Hackerrank GCD Product(莫比乌斯反演)
程序员文章站
2022-06-28 11:58:50
题意 "题目链接" Sol 一道咕咕咕了好长时间的题 题解可以看 "这里" cpp include define LL long long using namespace std; const int MAXN = 1e7 + 5e6 + 10, mod = 1e9 + 7, mod2 = 1e9 ......
题意
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 %d\n", 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 */