2020牛客暑期多校训练营(第四场)B-Basic Gcd Problem
程序员文章站
2022-04-01 16:11:11
...
传送门
Description
题解
实现
#include <bits/stdc++.h>
#define ll long long
const int N=1e6+10,mod=1e9+7;
using namespace std;
ll T,n,c;
bool np[N];
ll tot,p[N],mn[N];
ll ksm(ll a,ll b){ll r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod,b>>=1;}return r;}
void sieve(){
np[0]=np[1]=mn[1]=1;
for(int i=2;i<N;i++){
if(!np[i]) p[++tot]=i,mn[i]=i;
for(int j=1;j<=tot&&i*p[j]<N;j++){
np[i*p[j]]=1,mn[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}int main(){
sieve(),scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&c);
ll p=0;
while(n^1) n/=mn[n],++p;
printf("%lld\n",ksm(c,p));
}
}
上一篇: tf.cond报错Initializer for variable is from inside control-flow construct such as a loop or condition
推荐阅读
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第四场)F题
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
[2020牛客暑期多校训练营第三场] L.Problem L is the Only Lovely Problem 字符串函数
-
2020牛客暑期多校第四场 H - Harder Gcd Problem(思维/构造)
-
2020牛客暑期多校 第四场H-Harder Gcd Problem(思维,gcd)
-
2020牛客暑期多校训练营第四场Operating on the Tree
-
牛客多校第四场 H-Harder Gcd Problem【素数筛+贪心】
-
2020牛客暑期多校训练营(第四场)B-Basic Gcd Problem
-
2020牛客暑期多校训练营(第四场)D- Dividing Strings