2014
03-23

# Rotation

As you know, AekdyCoin loves games.One day，he got a small square board such as the one in Figure 1，the length of side is A (Here A is an integer!).
Now AekdyCoin has C different color, he uses these color to paint the A * A board above. You could see a possible painted board in Figure 2.
If one board could be rotated to another board (both painted), we consider them as the same, just as you could see in the figure 3。
Now，AekdyCoin cut the A*A board into A*A small square boards whose length of side is exactly 1.
Then AekdyCoin combine some squares to some new B*B squares(as many as possible)，here :
B * B * K + 1 = A * A, (K >= 0)
in the figure 5, there are two possible ways, B = 1 or B = 2
Then AekdyCoin connect the left one 1 * 1 square to other B * B square(s), as in the figure 6
But all the state you get if you rotate any B * B square(s) or rotate the figure around the left one 1 * 1 square are considered as the same. For example, all the states in Figure 7 are same.
Now AekdyCoin want to know the unique state he could get if he try any possible combination .(That means he will try all possible B)

The first line is an integer T indicates the number of the cases. ( T <= 1000)
Then T lines
A C
Indicate the value of A and the kind of colors AekdyCoin has. (1<=A,C<=10^9)

The first line is an integer T indicates the number of the cases. ( T <= 1000)
Then T lines
A C
Indicate the value of A and the kind of colors AekdyCoin has. (1<=A,C<=10^9)

2
2 7
3 2

Case 1: 833
Case 2: 114

by—cxlove

http://acm.hdu.edu.cn/showproblem.php?pid=3441

#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;
}

1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
for (j = adj .begin(); j != adj .end(); ++j)
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？

2. #include <cstdio>

int main() {
//answer must be odd
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}