邬澄瑶的公约数

公约数"/>

邬澄瑶的公约数

不能先对所有底数求ans = gcd(ans,xi)，再求每个xi^pi有多少个ans,这样得到的答案是错误的。

例如样例

输入
2
8 4
2 3
输出
64

结果自己那样做输出16

就是没考虑ans = gcd(ans,xi)后xi/ans剩下的数，p次方后可以得到ans,
比如 x =8,p = 2, x /4 = 2;2^2 = 4;

正确的方法是对底数x进行质因数分解
x = abc……
x^p = a^p * b^p * c^p……;
所以只要记录每个质因数的最小底数Pmin就可以得到
ans = a^Pmin * b^Pmin……；
ans%mod就是最终答案,求幂用上快速幂即可并且边乘边mod

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num[20000][2];//x,p
ll key[20000];//下标为质因数，存最小质因数指数
ll mod = 1e9 + 7;ll min(ll x,ll y){return x < y? x:y;
}
ll max(ll x,ll y){return x < y? y:x;
}
ll qqow(ll x,ll y){ll ans = 1;while(y){if(y & 1)ans = ans*x%mod;x = x*x%mod;y>>=1;}return ans;
}
int main(){ll n;ll ans = 1;ll x;cin >> n;for(int i = 0;i < n;i++){cin >> num[i][0];}for(int i = 0;i <= 20000;i++)key[i] = 10000000;for(int i = 0;i < n;i++)cin >> num[i][1];for(int i = 0;i < n;i++){for(ll j= 2;j <= 10000;j++){x = 0;while(num[i][0]%j == 0){num[i][0]/=j;x++;}key[j] = min(key[j],x*num[i][1]);//确保每个质因数都覆盖，如果质因数不是x的因数，那么该质因数的指数就应该是0}}for(int i = 2;i <= 10000;i++){if(key[i])ans = ans * qqow(i,key[i])%mod;}cout << ans%mod << endl;return 0;
}