題目：有一個A*A的正方形，拆成A*A個1*1的小正方形，然後組成k個B*B的正方形，而且剩下一個小正方形，也就是A*A=K*B*B+1。中間小小正方形連到K個B*B正方形的形狀有多少種，有C種顏色，而且旋轉視為等價。
拿下AC的身體，開心吖，不過跪舔 了好久。
思路： 找到B，然後對B*B的正方形進行染色，然後將每一種染色方案視為一種顏色。將K個B*B的正方形看成K個物品的環，用之前得到的顏色進行染色。中間的小方塊有C種顏色可選 。
那麼第一步：找到B，直接分解肯定不行，A*A-1達到10^18左右，可以分解成(A-1)(A+1),分別找到因子，然後再合並在一起，然後搜索所有的因子，得到可能的B。
第二步：對於得到的B，進行B*B的正方形的染色，這個很基礎了，4種旋轉，C^(B*B)+2*C^((B*B+3)/4)+C^((B*B+1)/2);
然後再乘以4的逆元，若這步的方案是Cnt_B
第三步：那麼剩下的相當於對K個物品的環進行染色，顏色數量為Cnt_B,也是基礎的Polya,但是有一點，當B比較小，那麼K就會非常大，可能達到10^18的級別，那麼即使用歐拉函數優化，sqrt(K)也接受不了，之前我們已經找過A*A-1的因子，一部分給了B*B，剩下的為K的，那麼直接對剩下的質因子搜索即可。所以在第一步搜索的時候把B*B的因子去掉，不過記得還原現場。這一步的實現就是進行第二次搜索，第二次Polya。
注意：糾結了好久，由於范圍很大，時刻注意溢出問題，級別大部分都是10^18，記得取模後再乘
在歐拉函數的時候，用素數表還是會TLE，同樣是利用之前分解因子得到的因子表。
[cpp]
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 1<<29
#define LL long long
#define N 1000000000
#define MOD 1000000007
#define pb(a) push_back(a)
using namespace std;
int tot;
LL A,c;
LL inverse_4,inverse_k;
int prime[40000],cnt=0;
LL fac[1000][2];
bool flag[40000]={0};
vector<int>v;
void Prime(){
for(int i=2;i<=sqrt(N+1.0);i++){
if(flag[i]) continue;
prime[cnt++]=i;
for(int j=2;j*i<=sqrt(N+1.0);j++)
flag[i*j]=true;
}
}
//以上素數表
LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(b==0){x=1;y=0;return a;}
LL gcd=extend_gcd(b,a%b,x,y);
LL t=x;x=y;
y=t-a/b*y;
return gcd;
}
LL Get_inverse(LL num){
LL x,y;
LL gcd=extend_gcd(num,MOD,x,y);
return (x%MOD+MOD)%MOD;
}
//以上求逆元
LL Eular(LL n){
LL ret=1;
for(int i=0;i<tot&&fac[i][0]*fac[i][0]<=n;i++){
if(n%fac[i][0]==0){
n/=fac[i][0];ret*=fac[i][0]-1;
while(n%fac[i][0]==0){n/=fac[i][0];ret*=fac[i][0];}
}
}
if(n>1) ret*=n-1;
return (ret%MOD);
}
//以上求歐拉函數，注意要直接用之前分解的因子，不然會TLE
LL PowMod(LL a,LL b){
LL ret=1;
a%=MOD;
while(b){
if(b&1) ret=((LL)ret*a)%MOD;
a=((LL)a*a)%MOD;
b>>=1;
}
return ret;
}
//快速冪
void get_fact(LL t){
for(int i=0;i<cnt&&prime[i]*prime[i]<=t;i++){
while(t%prime[i]==0){
t/=prime[i];
v.pb(prime[i]);
}
}
if(t>1) v.pb(t);
}
//分解因子
void get_union(){
sort(v.begin(),v.end());
tot=0;
fac[tot][0]=v[0];fac[tot++][1]=1;
for(int i=1;i<v.size();i++){
if(v[i]==fac[tot-1][0])
fac[tot-1][1]++;
else{
fac[tot][0]=v[i];
fac[tot++][1]=1;
}
}
}
//將A-1和A+1的因子整合在一起
LL ret_A;
void dfs(int idx,LL num,LL cnt_B,LL K){
if(idx>=tot){
ret_A=(ret_A+PowMod(cnt_B,K/num)*Eular(num)%MOD)%MOD;
return ;
}
for(int i=0;i<=fac[idx][1];i++){
dfs(idx+1,num,cnt_B,K);
num*=fac[idx][0];
}
}
//搜索K的因子，歐拉函數優化，第二個Polya
LL get_A(LL K,LL cnt_B){
ret_A=0;
dfs(0,1,cnt_B,K);
return (((ret_A*inverse_k)%MOD)*c)%MOD;
}
//用B*B的數量給K個環染色
LL get_B(LL B){
LL ans=PowMod(c,(LL)B*B);
ans=(ans+2*PowMod(c,((LL)B*B+3)/4))%MOD;
ans=(ans+PowMod(c,((LL)B*B+1)/2))%MOD;
return (ans*inverse_4)%MOD;
}
//B*B的正方形染色,4種旋轉
LL ans;
void dfsB(int idx ,LL nowB){
if(idx>=tot){
LL cnt_B=get_B(nowB);
LL K=(A*A-1)/nowB/nowB;
inverse_k=Get_inverse(K);
ans=(ans+get_A(K,cnt_B))%MOD;
return ;
}
LL temp=fac[idx][1];
//因子每次減少2，因為是B*B，而且剩余的用作搜索K的因子
for(int i=0;i<=temp;i+=2,fac[idx][1]-=2){
dfsB(idx+1,nowB);
nowB*=fac[idx][0];
}
fac[idx][1]=temp;
}
//以上搜索B
LL slove(){
v.clear();
get_fact(A-1);
get_fact(A+1);
get_union();
ans=0;
dfsB(0,1);
return ans;
}
int main(){
int t,cas=0;
Prime();
inverse_4=Get_inverse(4);
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d",&A,&c);
printf("Case %d: ",++cas);
if(A==1) printf("%I64d\n",c);
else
printf("%I64d\n",slove());
}
return 0;
}
