数論+貪欲-Basic Gcd Problem-2020牛客夏休み多校訓練キャンプ(第4回)

数論+貪欲-Basic Gcd Problem-2020牛客夏休み多校訓練キャンプ(第4回)
タイトル:
与えられた式:
{ f c ( x ) = m a x 1 ≤ i ≤ x − 1 c ⋅ f c ( g c d ( i , x ) ) x > 1 f c ( x ) = 1 x = 1\begin{cases}f_c(x)=max_{1≤i≤x-1}c·f_c(gcd(i,x))\qquad x>1\\\\f_c(x)=1\qquad\qquad\qquad\qquad\qquad\qquad\quad x=1\end{cases} ⎩⎪⎨⎪⎧​fc​(x)=max1≤i≤x−1​c⋅fc​(gcd(i,x))x>1fc​(x)=1x=1​
T組のテストデータであり、各組は2つの正の整数nとcを含み、f c(n)を出力する.答えは1 0 9+7で型を取ります.T組のテストデータ、各組は2つの正の整数nとcを含んで、f_を出力しますc(n).答えは10^9+7で型を取ります.T組のテストデータであり、各組は2つの正の整数nとcを含み、fc(n)を出力する.答えは109+7で型を取ります.
データ範囲:
1 ≤ T ≤ 1 0 6 , 1 ≤ n , c ≤ 1 0 6 1≤T≤10^6,1≤n,c≤10^6 1≤T≤106,1≤n,c≤106
例1入力

2
3 3
10 5

しゅつりょく

3
25

分析:
f反復の回数kが多ければ多いほど良く,答えはc kであることが容易に解析された.f反復の回数kが多ければ多いほど良いと分析しやすく,答えはc^kである.f反復の回数kが多ければ多いほど良いと分析しやすく,答えはckである.
n=P 1 a 1 P 2 a 2を貪欲に考える.P k a kは、P 1

g cdの反復回数を最も多くするには、最小質量因子を毎回約1つ除去することが最適であり、このように総回数、すなわちすべての質量因子指数の和である.gcdの反復回数を最も多くするには、最小質量因子を毎回約1つ除去することが最適であり、このように総回数、すなわちすべての質量因子指数の和である.gcdの反復回数を最も多くするには、最小質量因子を毎回約1つ除去することが最適であり、このように総回数、すなわちすべての質量因子指数の和である.
問題:正の整数nをどのように急速に分解し、そのすべての質因子の指数の和を得るか.
本題T≦1 0 9,n≦1 0 6,n個毎に質量因数を分解すれば,時間複雑度O(n)もタイムアウトする,本題T≦10^9,n≦10^6,n個毎に質量因数を分解すれば,時間複雑度O(sqrt{n})もタイムアウトする,本題T≦109,n≦106,n個毎に質量因数を分解すれば,時間の複雑さがO(n)でもタイムアウトし、
したがって,前処理しか実現できない.したがって,前処理しか実現できない.したがって,前処理しか実現できない.
M[i]は正の整数iの全質量因子の指数の和を表すとする.M[i]は正の整数iのすべての質量因子の指数の和を表すとする.M[i]は正の整数iのすべての質量因子の指数の和を表すとする.
①、iが素数であればM[i]=1.①、iが素数であればM[i]=1とする.①、iが素数であればM[i]=1とする.
②、任意の合数に対して、その最小質量因子P jと別の数iとの積を分解する:P j× i,M[P j]× i ] + = M [ i ] + 1 . ②、任意の合数に対して、その最小質量因子P_を分解するjと他の数iとの積:P_j×i,M[P_j]×i]+=M[i]+1. ②、任意の合数に対して、その最小質量因子Pjと別の数iとの積を分解する:Pj×i,M[Pj]×i]+=M[i]+1.
従って,線形ふるいでM配列を繰返し求めることができる.従って,線形ふるいでM配列を繰返し求めることができる.従って,線形ふるいでM配列を繰返し求めることができる.
コード:

#include 
#include 
#include 
#include 
#include 
  
#define ll long long
  
using namespace std;
  
const int N=1e6+10, mod=1e9+7;

int primes[N],cnt,M[N];
bool st[N];

void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            primes[cnt++]=i;
            M[i]=1;
        }
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=true;
            M[primes[j]*i]+=M[i]+1;
            if(i%primes[j]==0) break;
        }
    }
}

int quick_pow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%mod;
        a=(ll)a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    get_prime(1e6);
    int T;
    int n,c;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&c);
        int k=M[n];
        printf("%d
",quick_pow(c,k));
    }
    
    return 0;
}