TrickGCD

solution

F ( n ) 表 示 [ g c d = = k n ] 的 个 数 ， k 属 于 Z + , F(n)表示[gcd==kn]的个数，k属于Z_+, F(n)表示[gcd==kn]的个数，k属于Z+​,

f ( n ) 表 示 [ g c d = = n ] 的 个 数 . f(n)表示[gcd ==n]的个数. f(n)表示[gcd==n]的个数.

F ( n ) = ∏ i = 1 n a i n F(n)=\prod\limits_{i=1}^{n}\frac{a_i}{n} F(n)=i=1∏n​nai​​

F ( n ) = ∑ n ∣ d f ( d ) = > f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) F(n)=\sum\limits_{n|d}f(d) =>f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})F(d) F(n)=n∣d∑​f(d)=>f(n)=n∣d∑​μ(nd​)F(d)

f ( 1 ) = ∑ n ∣ d μ ( d ) F ( d ) = ∑ i = 2 M A X μ ( d ) ∏ i = 1 d a i d f(1)=\sum\limits_{n|d}\mu(d)F(d)=\sum\limits_{i=2}^{MAX}\mu(d)\prod\limits_{i=1}^{d}\frac{a_i}{d} f(1)=n∣d∑​μ(d)F(d)=i=2∑MAX​μ(d)i=1∏d​dai​​

code

/*SiberianSquirrel*//*CuteKiloFish*/
#include <bits/stdc++.h>
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define Polynomial vector<int>
#define Inv(x) quick_pow(x, mod - 2)
#define DEBUG(x, y) cout << x << ": " << y << '\n';
using ll = long long;
using ull = unsigned long long;
//const ll mod = 998244353, mod_g = 3, img = 86583718;//NTT, 多项式三角形
const ll mod = 1e9 + 7;
const int N = int(6e5 + 10);

inline int add(int a, int b) {
    return a + b < mod? a + b: a + b - mod;
}
inline int sub(int a, int b) {
    return a - b < 0? a - b + mod: a - b;
}
inline int mul(int a, int b) {
    return 1ll * a * b % mod;
}

ll quick_pow(ll ans, ll p, ll res = 1) {
    for(; p; p >>= 1, ans = ans * ans % mod)
        if(p & 1) res = res * ans % mod;
    return res % mod;
}

int prime[int(2e5 + 10)], mu[int(2e5 + 10)], cnt;
bool vis[int(2e5 + 10)];

//  int fac[int(2e5 + 10)] = {1}, ifac[int(2e5 + 10)] ={1};

void init(int n) {
//    for(int i = 1; i <= n; ++ i) 1ll * fac[i] * i % mod, ifac[i] = Inv(fac[i]);
    mu[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        if(!vis[i]) prime[++ cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++ j) {
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            } else mu[i * prime[j]] = -mu[i];
        }
    }
}

inline void solve() {
    init(int(2e5));
    int o, cases = 0; cin >> o; while(o --) {
        int n; cin >> n;
        int minn = int(2e5 + 10), maxx = -1; ll res = 0;
        vector<int> num(int(2e5 + 10)); for(int i = 1, x; i <= n; ++ i) {
            cin >> x; num[x] ++;
            minn = min(minn, x);
            maxx = max(maxx, x);
        }
        for(int i = int(2e5); i > 0; -- i) num[i - 1] += num[i];
        for(int i = 2; i <= minn; ++ i) {
            if(!mu[i]) continue;
            ll temp = 1, now = 1;
            int p = i;
            while(p <= maxx) {
                temp = temp * quick_pow(now ++, num[p] - num[p + i]) % mod;
                p += i;
            }
            res = (res + -mu[i] * temp + mod) % mod;
        }
        cout << "Case #" << ++ cases << ": " << res << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
//    freopen("output", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#else
    solve();
#endif
    return 0;
}