题面
Let's introduce some definitions that will be needed later.
Let prime(x) be the set of prime divisors of x. For example, prime(140)={2,5,7}, prime(169)={13}.
Let g(x,p) be the maximum possible integer where k is an integer such that x is divisible by . For example:
- g(45,3)=9 (45 is divisible by =9 but not divisible by =27),
- g(63,7)=7 (63 is divisible by =7 but not divisible by =49).
Let f(x,y) be the product of g(y,p) for all p in prime(x). For example:
- f(30,70)=g(70,2)?g(70,3)?g(70,5)=??=10,
- f(525,63)=g(63,3)?g(63,5)?g(63,7)=??=63.
You have integers x and n. Calculate f(x,1)?f(x,2)?…?f(x,n)mod(+7).
Input
The only line contains integers x and n (2≤x≤, 1≤n≤) — the numbers used in formula.
Output
Print the answer.
Examples
input
10 2
output
2
input
20190929 1605
output
363165664input
947 987654321987654321
output
593574252Note
In the first example, f(10,1)=g(1,2)?g(1,5)=1, f(10,2)=g(2,2)?g(2,5)=2.
In the second example, actual value of formula is approximately 1.597?. Make sure you print the answer modulo (+7).
In the third example, be careful about overflow issue.
译
g(x,p)=(<=x,k取最大值)
f(x,y)=g(y,)?g(y,)?…?g(y,).(x=**…*)
求 f(x,1)?f(x,2)?…?f(x,n)mod(+7).
输入： x 和 n (2≤x≤, 1≤n≤)
思路
剖开题面，发现其实就是求g(1,p1)*…*g(n,p1)*g(1,p2)*…*g(n,p2)*g(…，px)
所以把x先质因数分解，之后发现计算的幂就是n/p的个数注意幂的次数还要模
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll unsigned __int64
#define mod 1000000007
ll powm(ll a,ll b)
{ll r=1,bas=a;while(b>0){if(b&1)r=r*bas%mod;bas=bas*bas%mod;b>>=1;}return r%mod;
}
int x,t=0;
ll n,a[105],ans=1;
int main()
{scanf("%d%lld",&x,&n);if(x%2==0)a[++t]=2;while(x%2==0)x/=2;for(int i=3;i*i<=x;i+=2)if(x%i==0){a[++t]=i;while(x%i==0)x/=i;}if(x>1)a[++t]=x;for(int i=1;i<=t;i++){ll k=a[i],nn=n,s=0;while(nn/k>0)nn/=k,s+=nn;s%=mod-1;ans=ans*powm(k,s)%mod;}printf("%lld",ans%mod);
}