任意數n可以寫成 n = p1^k1 * p2^k2 * p3^n3 * ....* pn^kn（p1,p2,...pn為質因數）
n^m 的約數 一定是 p1^m1 * p2 ^m2 *p3^m3 *....* *pn^mn (m1<k1*m,m2<k2*m,....mn<kn*m)
是以約數的和為(p1^0+p1^1+.....+p1^(m*k1))*(p2^0+p2^1+...+p2^(m*k2))*......*(pn^0+pn^1+...+pn^(m*kn))
該多項式展後每一項都為一個約數。
對n^m%mod 可以轉換為(n^2)^(m/2)%mod * n^(m%2) %mod = (n^2%mod)^m/2%mod * n^(m%2)%mod
對于前n項和求模，可轉為前n/2項 * (1+p^n/2)，及可通過遞歸求解
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int mod = 1000000007;
int prime[70000];
int trueprime[70000];
int count = 0;
long long ans=1;
long long yu = 1;
long long powMod(long long m,long long n)
{
yu = 1;
while(n)
{
if(n%2==1)
yu = (yu*m)%mod;
m = m*m%mod;
n/=2;
}
return yu;
}
long long sumMod(long long m,long long n)
{
if(n==0)
return 1;
else if(n==1)
{
return (m+1)%mod;
}
else if(n%2==0)
{
return (((powMod(m,n/2)+1)*sumMod(m,n/2-1))%mod + powMod(m,n)%mod)%mod;
}
else
{
return ((powMod(m,n/2+1)+1)*sumMod(m,n/2))%mod;
}
}
void make_prime()
{
for(int i = 2;i<70000;i++)
{
if(prime[i]==0)
{
if(i < sqrt(70000.0))
{
for(int j = i*i;j<70000;j+=i)
{
prime[j] = 1;
}
}
trueprime[count++] = i;
}
}
}
void getmi(long long m,long long n)
{
for(int i = 0;i<count&&prime[i]*prime[i]<=m;i++)
{
long long mi = 0;
while(m%trueprime[i]==0)
{
mi++;
m /= trueprime[i];
}
mi*=n;
if(mi!=0)
ans = ans*sumMod(trueprime[i],mi)%mod;
}
if(m>1)
ans = ans*sumMod(m,n)%mod;
}
int main()
{
int m;
make_prime();
long long p,q;
scanf("%d",&m);
for(int i = 1;i<=m;i++)
{
ans = 1;
scanf("%lld %lld",&p,&q);
getmi(p,q);
printf("Case %d: %lld\n",i,ans);
}
return 0;
}