欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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
*/