newcoder 周赛143 C 费马小定理和质因数分解相关优化
原文链接：https://www.cnblogs.com/Time25/p/20026182.html
zhe ta ma shi C ti gai you de yang zi ma费马小定理
代码及其注释
https://ac.nowcoder.com/acm/contest/134529/C
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using namespace std;
//"O campeão tem nome, e se chama Charles Oliveira!"
const int N=200005;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
/**
* 思路大概就是给一个X和Y，要求得是这两个数字相乘得结果得质因数A A^A的和
* 比如假设X*Y=20的结果就是1*1+2*2+4*4+......20*20
* 如果硬算的话，因为X和Y的数据范围都是1e9+7，把两个乘起来用根号来求质因数还是会T
*
* 可以知道假设 x*y=A1^x1+A2^x2+A3^x3.......,那么x*y的所有可以约的数就是A1^y+A2^y1+A3^y3......
* 这里的y可以是0次，一次，2次.....fac[A1]
* 这里的y1可以是0次，一次，2次......fac[A2]
*
* 如果都是0次，那么就是1了，一个也不选那么就是1，1也正好是范围内的数字
*/
int fastpower(int base,int exp){
int res=1;
base%=MOD;
while(exp){
if(exp&1)res=(res*base)%MOD;
base=(base*base)%MOD;
exp>>=1;
}
return res;
}
map<int,int>fac;
void factors(int x){
for(int i=2;i*i<=x;i++){
while(x%i==0)
{
fac[i]++;
x/=i;
}
}
if(x>1)fac[x]++;//注意这里没有包含1！
//因为下面dfs就是从1开始的，只要一路dfs下去一个都不选，就是ans+=1;
}
vector<pair<int,int>>v;
int total_ans=0;
void dfs(int idx,int d){
if(idx==v.size()){
if(d%MOD==0)return ;
//费马小定理
else total_ans=(total_ans+fastpower(d%MOD,d%(MOD-1)))%MOD;
return ;
}
int cnt=v[idx].second;
int poww=1;
//这个for loop从0开始就是考虑到了可以一个都不选，也就是选一个到选cnt个加上1个什么都不选
for(int i=0;i<=cnt;i++){
dfs(idx+1,d*poww);
if(i<cnt)poww*=v[idx].first;
//这里不可以写成poww=(poww*v[idx].first)%MOD;
//原因就是这样传入就变成了fastpower(d%mod%mod,d%mod%(mod-1))！=fastpower(d%mod,d%(mod-1));
}
}
void solve(){
int x,y;
cin>>x>>y;
factors(x);
factors(y);
for(auto &[x,y]:fac){
v.push_back({x,y});
}
dfs(0,1);
cout<<total_ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
//cin>>t;
while(t--)solve();
}
