元旦快乐！！！

原题链接：https://leetcode.cn/contest/weekly-contest-326

统计能整除数字的位数

class Solution {
public:
    int countDigits(int num) {
        int t=num, res=0;
        while(num){
            if(t%(num%10) == 0) res++;
            num/=10;
        }
        
        return res;
    }
};

数组乘积中的不同质因数数目

注意边乘边筛质因子

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_map<int, int> mp;
        
        for(auto val: nums)
        {
            int n=val;
            for(int i=2; i<=n/i; i++)
                while(n%i==0) n/=i, mp[i]++;
            if(n>1) mp[n]++;
        }
        
        return mp.size();
    }
};

将字符串分割成值不超过 K 的子字符串

贪心

class Solution {
public:
    int minimumPartition(string s, int k) {
        int res=0, sum=0;
        int n=s.size();
        for(int i=0; i<n; i++){
            int x=s[i]-'0';
            if(x>k) return -1;
            if(x+1ll*sum*10 <= k) sum=sum*10+x;
            else res++, sum=x;
        }
        
        if(sum) res++;
        return res;
    }
};

范围内最接近的两个质数

把 $[1, right]$ 之间的质数全部筛出来，然后对满足条件的逐一比较。

class Solution {
public:
    int primes[1000010], cnt;
    bool st[1000010];
    void euler(int n)
    {
        for(int i=2;i<=n;i++)
        {
            if(!st[i]) primes[cnt++]=i;
            for(int j=0;j<cnt&&primes[j]*i<=n;j++)
            {
                st[i*primes[j]]=true;
                if(i%primes[j]==0) break;
            }
        }
    }
    vector<int> closestPrimes(int left, int right) {
        euler(right);
        
        int k=-1, minv=0x3f3f3f3f;
        for(int i=0;i<cnt;i++){
            if(primes[i]>=left && i-1>=0 && primes[i-1]>=left) {
                if(primes[i]-primes[i-1]<minv) {
                    k=i, minv=primes[i]-primes[i-1];
                }
            }
        }
        if(minv==0x3f3f3f3f) return {-1, -1};

        return {primes[k-1], primes[k]};
    }
};