题目描述
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; }