# 鹏鹏的旧OI博客

## 题目描述

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As you can deduce from the company name, their business is beads. Their PR department found out that customers are interested in buying colored bracelets. However, over 90 percent of the target audience insists that the bracelets be unique. (Just imagine what happened if two women showed up at the same party wearing identical bracelets!) It's a good thing that bracelets can have different lengths and need not be made of beads of one color. Help the boss estimating maximum profit by calculating how many different bracelets can be produced.
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.

## 输入

Every line of the input file defines a test case and contains two integers: the number of available colors c followed by the length of the bracelets s. Input is terminated by c=s=0. Otherwise, both are positive, and, due to technical difficulties in the bracelet-fabrication-machine, cs<=32, i.e. their product does not exceed 32.

## 输出

For each test case output on a single line the number of unique bracelets. The figure below shows the 8 different bracelets that can be made with 2 colors and 5 beads.

1 1
2 1
2 2
5 1
2 5
2 6
6 2
0 0

1
2
3
5
8
13
21

## 来源

POJ2409

1° 此时以相邻两个珠子之间的点连线作为对称轴

2° 此时以相对的两个珠子连线作为对称轴

#include<cstdio>
#include<cmath>
using namespace std;
int m,n;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
while(~scanf("%d%d",&m,&n)&&m&&n){
int ans=0;
for(int i=1;i<=n;++i)ans+=pow(m,gcd(n,i));
if(n&1)ans+=n*pow(m,(n+1)/2);
else ans+=n/2*(pow(m,n/2+1)+pow(m,n/2));
printf("%d\n",ans/2/n);
}
return 0;
}

## 题目描述

On of Vance's favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.
In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

## 输入

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

## 输出

For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

2
3 4
1 2

Case #1: 21
Case #2: 1

## 来源

HDU3923

#include<cstdio>
using namespace std;
const long long MOD=1000000007ll;
int n,m;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long pow(int a,int b){
long long r=1ll,base=(long long)a;
while(b){
if(b&1)(r*=base)%=MOD;
(base*=base)%=MOD;b>>=1;
}
return r;
}
int ex_gcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return a;}
ex_gcd(b,a%b,y,x);
y-=a/b*x;
}
int main(){
int t;scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d%d",&n,&m);
printf("Case #%d: ",i);
long long ans=0;
for(int i=1;i<=m;++i)(ans+=pow(n,gcd(m,i)))%=MOD;
if(m&1)(ans+=m*pow(n,(m+1)/2))%=MOD;
else (ans+=m/2*(pow(n,m/2+1)+pow(n,m/2)))%=MOD;
int x,y;ex_gcd(2*m,MOD,x,y);
while(x<0)x+=MOD;
printf("%I64d\n",(ans*(long long)x)%MOD);
}
return 0;
}