1 条题解

  • 0
    @ 2021-11-21 17:27:40
    #include <iostream>
    #include <vector>
    typedef long long ll;
    using namespace std;
    const int mod = 1000000007;
    ll n, k;
    int main()
    {
        cin >> n >> k;
        vector<bool> primes(1e6 + 10, true);
        vector<int> primess;
        for (int i = 2; i * i < primes.size(); ++i) {
            if (primes[i]) {
                int j = 2 * i;
                while (j < primes.size()) {
                    primes[j] = false;
                    j += i;
                }
            }
        }
        // Get all primes.
        for (int i = 2; i < primes.size(); ++i) {
            if (primes[i]) {
                primess.push_back(i);
            }
        }
        vector<int> small = vector<int>(k + 1, 0);
        for (int i = 0; i < small.size(); ++i)
            small[i] = i + 1;
        vector<ll> big = vector<ll>(k + 1, 0);
        for (int i = 0; i < big.size(); ++i)
            big[i] = n - k + 1 + i;
        ll ans = 1;
        for (auto p : primess) {
            // consider small
            int tmp = 0;
            for (int i = p - 1; i < k; i += p) {
                while (small[i] % p == 0) {
                    --tmp;
                    small[i] /= p;
                }
            }
            // consider big
            for (int i = ((n - k + 1) / p * p) - (n - k + 1); i < k; i += p) {
                if (i < 0)
                    continue;
                while (big[i] % p == 0) {
                    ++tmp;
                    big[i] /= p;
                }
            }
            ans = ans * (tmp + 1) % mod;
        }
        for (int i = 0; i < k; ++i) {
            if (big[i] > 1) {
                ans = ans * 2 % mod;
            }
        }
        cout << ans << endl;
        return 0;
    }
    
    
  • 1

信息

ID
1303
难度
9
分类
(无)
标签
递交数
97
已通过
4
通过率
4%
被复制
1
上传者