c/c++语言开发共享Hackerrank GCD Product(莫比乌斯反演)

题意

sol

一道咕咕咕了好长时间的题

题解可以看

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e7 + 5e6 + 10,  mod = 1e9 + 7, mod2 = 1e9 + 6; int n, m, vis[maxn], prime[maxn], mu[maxn], f[maxn], tot; int add(int x, int y) {     if(x + y < 0) return x + y + mod;     return x + y >= mod ? x + y - mod : x + y; } int mul(int x, int y) {     return 1ll * x * y % mod; } int fp(int a, int p) {     int base = 1;     while(p) {         if(p & 1) base = mul(base, a);         a = mul(a, a); p >>= 1;     }     return base; } void sieve(int n) {     vis[1] = 1; mu[1] = 1;     for(int i = 2; i <= n; i++) {         if(!vis[i]) prime[++tot] = i, mu[i] = -1;         for(int j = 1; j <= tot && i * prime[j] <= n; j++) {             vis[i * prime[j]] = 1;             if(!(i % prime[j])) {mu[i * prime[j]] = 0; break;}             else mu[i * prime[j]] = -mu[i];         }     }     for(int i = 1; i <= tot; i++)          for(ll j = prime[i]; j <= n; j *= prime[i])             f[j] =prime[i];     for(int i = 1; i <= n; i++) if(!f[i]) f[i] = 1; } signed main() {     cin >> n >> m;     sieve(1e7 + 5e6);     //for(int i = 1; i <= 100; i++) printf("%d %dn", i, f[i]);     int ans = 1;     for(int i = 1; i <= n; i++) {         if(f[i] == 1) continue;         ans = mul(ans, fp(f[i], 1ll * (n / i) * (m / i) % mod2));     }     cout << ans;     return 0; } /* 100000 50000 200 300 100 2 1 1 */