题目描述
As a great ACMer, ZYB is also good at math and number theory.
ZYB constructs a function f_c(x) such that:
Give some positive integer pairs , ZYB wants to know
.
输入描述
The input contains multiple test cases. The first line of input contains one integer
.
In the following lines, each line contains two integers
describing one question.
输出描述
For each test case, output one integer indicating the answer.
示例1
输入
2 3 3 10 5
输出
3 25
分析
题目给出了一个可递归求解的函数,递归停止的条件为:当 ,
。递推式为
,
可以看作常数,若递归了
次,那么就会产生乘子
。由于每次递归都取
,所以递归的次数要尽量多(也就是让乘子尽量大)。最多可以递归 显然,若
最多可以递归
次,则
,我们要求的就是最大的递归次数。
递归次数显然与 有关。由算数基本定理,当
,可以将
写成多个质数的乘积,不妨设
,质因子个数为
。经过一次递归,就会求一次
,就会损失一定数量的质因子。如果每次递归只损失一个质因子,那么递归次数显然是最多的,为
;这样的方案是存在的,比如说
。
综上所述,,
为
的质因子数量。
若每组测试数据单独求质因子数量,时间复杂度为 ,会
。不妨直接用欧拉筛在线性时间内得到
内各个整数的质因子数量。若
为质数,那么
;若
为合数,有递推式
,其中
为质数。
代码
/****************************************************************** Copyright: 11D_Beyonder All Rights Reserved Author: 11D_Beyonder Problem ID: 2020牛客暑期多校训练营(第四场) Problem B Date: 8/15/2020 Description: Euler Sieve And GCD *******************************************************************/ #include<iostream> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int N=1000006; const int mod=1000000007; int _; bool isprime[N]; ll prime[N>>1]; ll cnt[N]; void EulerSieve(int); ll qpow_mod(ll,int); int main(){ EulerSieve(1000000); for(cin>>_;_;_--){ int n,c; scanf("%d%d",&n,&c); printf("%lld\n",qpow_mod(c,cnt[n])); } return 0; } void EulerSieve(int maximum){ memset(isprime,true,sizeof(isprime)); int num=0; ll i,j; for(i=2;i<=maximum;i++){ if(isprime[i]){ prime[++num]=i; cnt[i]=1; } for(j=1;j<=num&&i*prime[j]<=maximum;j++){ isprime[i*prime[j]]=false; cnt[i*prime[j]]=cnt[i]+1; if(i%prime[j]==0){ break; } } } } ll qpow_mod(ll a,int b){ ll res=1; while(b){ if(b&1){ res=res*a%mod; } a=a*a%mod; b>>=1; } return res; }