大致题意：总共有A*A个小方格，有C种颜色。你要把着A*A个小方格拆乘K+1个部分，其中K个部分是B*B的正方形，剩下的一个单独的方格。要求着K个大正方形都连着这个单独的小方格成一个圈。现在你要用这C种颜色个小方格染色，使得每一个B*B的正方形内部要在旋转的时候本质不同，然后这个K个大正方形与中间的小方格在旋转的时候也要本质不同。问你本质不同的方案数。
这个比较显然的是一个需要用到两个Polya的题目。首先，这B*B的大正方形内部需要用一个Polya，总共有四种置换，分别对应旋转0°、90°、180°和270°。考虑每种旋转的时候的循环个数，分别是B*B个、(B*B+3)/4个、(B*B+1)/2个和(B*B+3)/4个。然后对于每一个循环个数，用C种颜色去填充，最后除以置换群数目４即可。这个就是对于特定的B，B*B方格的填充方案。我们不妨设这个填充方案是ｘ。
然后就是这Ｋ个B*B的格子，在连接中间小个子摆放的时候也要本质不同。那么这个问题，就相当于是一个包含K个珠子的项链，然后去染色也要求旋转的情况下本质不同的问题。但是这里，这个颜色数目，就恰好是我们B*B的格子的填充方案数x。有了这个转换，我们直接按照项链那么去做即可。
注意到本题的数据范围A可以到1e9，那么对应的A*A可以到1e18的级别。然后我们做的时候需要对所有的满足条件的B和K去做，那么满足A*A-1=B*B*K，相当于B*B是A*A-1的因子。但是A*A很大，即使用根号的复杂度求因子也会TLE，所以考虑把A*A-1拆成(A-1)(A+1)，然后求A-1和A+1的质因子，两个质因子再合并，之后质因子的组合就是因子。我们用dfs组合质因子，枚举出所有可能的B和K，然后求出x，再当作项链去做。当作项链的时候，也是需要枚举K个的因子，这个因子同样也可以用dfs组合质因子的方式，而且这个质因子恰好就是(A*A-1)/B/B的质因子，即在(A*A-1)的基础上，把B*B的质因子减去。最后求欧拉函数的时候也可以用这个来优化常数。时间复杂度不太好算，大概是?其实我也不知道，反正很快，93ms跑完，具体见代码：
#include<bits/stdc++.h> #define LL long long #define mod 1000000007 #define pb push_back #define lb lower_bound #define ub upper_bound #define INF 0x3f3f3f3f #define sf(x) scanf("%d",&x) #include <ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define sc(x,y,z) scanf("%d%d%d",&x,&y,&z) #define clr(x,n) memset(x,0,sizeof(x[0])*(n+5)) #define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout) using namespace __gnu_pbds; using namespace std; const int N = 1e5 + 10; const LL inv4 = 250000002; int n,m,sz,tot,ans,ansA,p[N],phi[N],fac[20],a[20]; gp_hash_table<int,int> pri; bool isp[N]; void init() { sz=0; phi[1]=1; for(int i=2;i<N;i++) { if (!isp[i]) p[++sz]=i,phi[i]=i-1; for(int j=1;j<=sz&&p[j]*i<N;j++) { int x=i*p[j]; isp[x]=1; if (i%p[j]==0) { phi[x]=phi[i]*p[j]%mod; break; } else phi[x]=phi[i]*(p[j]-1); } } } inline void getp(int x) { for(int i=1;p[i]*p[i]<=x&&i<=sz;i++) { if (x%p[i]) continue; int tmp=0; while(x%p[i]==0) x/=p[i],tmp++; pri[p[i]]+=tmp; } if (x>1) pri[x]++; } inline LL qpow(LL x,LL n) { LL res=1; x%=mod; n%=(mod-1); while(n) { if (n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } inline LL getphi(LL x) { LL res=1,xx=x; if (x<N) return phi[x]; for(int i=1;i<=tot&&(LL)fac[i]*fac[i]<=x;i++) { if (x