Let’s introduce some definitions that will be needed later.
Let ??????????(??) be the set of prime divisors of ??. For example, ??????????(140)={2,5,7}, ??????????(169)={13}.
Let ??(??,??) be the maximum possible integer ???? where ?? is an integer such that ?? is divisible by ????. For example:
??(45,3)=9 (45 is divisible by 32=9 but not divisible by 33=27),
??(63,7)=7 (63 is divisible by 71=7 but not divisible by 72=49).
Let ??(??,??) be the product of ??(??,??) for all ?? in ??????????(??). For example:
??(30,70)=??(70,2)⋅??(70,3)⋅??(70,5)=21⋅30⋅51=10,
??(525,63)=??(63,3)⋅??(63,5)⋅??(63,7)=32⋅50⋅71=63.
You have integers ?? and ??. Calculate ??(??,1)⋅??(??,2)⋅…⋅??(??,??)mod(109+7).
Input
The only line contains integers ?? and ?? (2≤??≤109, 1≤??≤1018) — the numbers used in formula.
Output
Print the answer.
Examples
inputCopy
10 2
outputCopy
2
inputCopy
20190929 1605
outputCopy
363165664
inputCopy
947 987654321987654321
outputCopy
593574252
Note
In the first example, ??(10,1)=??(1,2)⋅??(1,5)=1, ??(10,2)=??(2,2)⋅??(2,5)=2.
In the second example, actual value of formula is approximately 1.597⋅10171. Make sure you print the answer modulo (109+7).
In the third example, be careful about overflow issue.
思路：求出x的素因子，求其在1-n中所有数的贡献
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-10 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int MAXN = 150000 + 5; const int mod = 1e9 + 7; vector<LL>v; LL qpow(LL a,LL b) { LL res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } void primeFactor(LL n){ LL tmp = n; if(n % 2 == 0) { v.push_back(2); while (n % 2 == 0) { n /= 2; } } for(LL i = 3; i * i <= tmp; i += 2){ if(n % i == 0) { v.push_back(i); } while(n % i == 0){ n /= i; } } if(n > 2) v.push_back(n); } int main() { LL x,n; cin >> x; cin >> n; primeFactor(x); LL ans = 1; for(int i = 0; i < v.size(); i++) { LL tt = 0,nn = n; while(nn > 0) { nn /= v[i]; tt += nn; } ans = (ans % mod * qpow(v[i],tt)) % mod; } cout << ans << endl; }
CF1228C. Primes and Multiplication（数学）
原文：https://www.cnblogs.com/smallhester/p/11614893.html
