牛客contest5669-B

传送门

题目大意

现有函数

给定一些正整数对(ni, ci)，输出fci(ni)在模1e9+7意义下的函数值。

思路

观察公式不难看出f_c(x)=c^k，k与函数递归次数相关。要求到最大值，贪心的想法是尽可能多地递归，这样就能累乘到更多的c。最好的情况是每次递归都只消去一个 质因子，这样k=质因子的个数。

实现上，从x开始递归 ，找每个数除了自己外最大的因数，直到当前数是质数或1。记录这个过程中递归层数，这个层数就是k。可以先预存好值来提升效率。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; 

const int LIM = 1e6 + 10;
const ll MOD = 1e9 + 7;

//arr[i]中存i的质因子个数 
int	arr[LIM], t, n, c;

ll powMod( ll x, int y )
{
	ll ans = 1;
	
	while ( y )
	{
		if ( y & 1 ) ans = ans * x % MOD;
		
		y >>= 1;
		x = x * x % MOD;
	}
	
	return ans;
}

void findPrimeFactors( int x )
{
	if ( arr[x] )
		return;
		
	for ( int i = 2; i*i <= x; i++ )
	{
		if ( !(x % i) )
		{
			int tmp = x / i;
			findPrimeFactors( tmp );
			arr[x] = arr[tmp] + 1;
			return;
		}	
	}
	
	arr[x] = 1;
	return;
}

int main()
{
	arr[1] = 0;
	for ( int i = 2; i <= LIM; i++ )
		findPrimeFactors( i );

	scanf( "%d", &t );

	while ( t-- )
	{
		scanf( "%d%d", &n, &c );
		printf( "%lld\n", powMod( 1ll * c, arr[n] ) );
	}
	
	return 0;
}