题意
题目链接
Sol
一道咕咕咕了好长时间的题
题解可以看这里
代码语言：javascript复制#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
*/
