2020牛客暑期多校训练营（第四场）B

题目描述

  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;
}