zhe ta ma shi C ti gai you de yang zi ma
费马小定理
代码及其注释
https://ac.nowcoder.com/acm/contest/134529/C
#include<bits/stdc++.h>
using namespace std;
//"O campeão tem nome, e se chama Charles Oliveira!"
#define int long long
#define endl '\n'
#define ep emplace
#define pob
#define ll long long
#define pb push_back
#define pof pop_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define mod 998244353
#define MOD 1000000007
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();
}