ArifinDhaka(FirstLovePart2)

Problem L Arif inDhaka(First Love Part 2) Input: standard input Output: standard output Time Limit: 2 seconds Our hero Arif is now inDhaka(Look at problem10244 – First Loveif you want to know more about Arif, but that information is not n

Problem L

Arif in Dhaka (First Love Part 2)

Input: standard input

Output: standard output

Time Limit: 2 seconds

Our hero Arif is now in Dhaka (Look at problem 10244 – First Love if you want to know more about Arif, but that information is not necessary for this problem. In short, Arif is a brilliant programmer working at IBM) and he is looking for his first love. Days pass by but his destiny theory is not working anymore, which means that he is yet to meet his first love. He then decides to roam around Dhaka on a rickshaw (A slow vehicle pulled by human power), running DFS (by physical movement) and BFS (with his eyes) on every corner of the street and market places to increase his probability of reaching his goal. While roaming around Dhaka he discovers an interesting necklace shop. There he finds some interesting necklace/bracelet construction sets. He decides to buy some of them, but his programmer mind starts looking for other problems. He wants to find out how many different necklace/bracelet can be made with a certain construction set. You are requested to help him again. The following things are true for a necklace/bracelet construction set.

a) All necklace/bracelet construction sets has a frame, which has N slots to place N beads.

b) All the slots must be filled to make a necklace/bracelet.

c) There are t types of beads in a set. N beads of each type are there in the box. So the total number of beads is tN (t multiplied by N), of which exactly N can be used at a time.

Fig: Different types of necklace for t=2 and different value of N

The figure above shows necklaces for some different values of N (Here, t is always 2). Now let’s turn out attentions to bracelets. A bracelet is a necklace that can be turned over (A junior programmer in Bangladesh says that wrist watch is a necklace (Boys!!! Don’t mind :-))). So for abracelet the following two arrangements are equivalent. Similarly, all other opposite orientation or mirror images are equivalent.

So, given the description of a necklace/bracelet construction set you will have to determine how many different necklace and bracelet can be formed with made with that set

Input

The input file contains several lines of input. Each line contains two positive integers N(0

Output

For each line of input produce one line of output which contains two round numbers NN and NB separated by a single space, where NN is the number of total possible necklaces and NB is the number of total possible bracelets for the corresponding input set.

Sample Input

5 2

5 3

5 4

5 5

Sample Output

8 8

51 39

208 136

629 377

改代码需要处理一下数的幂不然在运算过程中会有数据的溢出影响结果

关于详解看书；

因为i可以从1到n得到n个置换 所以结果要除以n

又因为对于手镯存在翻转 奇数有n个对称轴即n个置换

偶数有n/2 + n/2共n个对称轴也是n个置换

（注：本题中注明了n和t大于0，如果在一般题目中没有注明，那么一定要考虑n==0的情况）

所以结果要除以2n

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
LL power[20];//power[i] = pow(t,i)
int gcd(int x,int y)
{
 while(x!=y)
 {
 if(x>y)
 x = x - y;
 else
 y = y - x;
 }
 return x;
}
int main()
{

 int n,t;
 while(scanf("%d%d",&n,&t)==2)
 {
 LL sum = 0;
 power[0] = 1;
 for(int i = 1;i<=n;++i)
 power[i] = power[i-1]*t;
 for(int i = 1;i<=n;++i)
 sum += power[gcd(i,n)];
 LL sum1 = 0;
 if(n%2==1)
 {
 sum1 = n*power[(n+1)/2];

 }else
 {
 sum1 = n/2*power[n/2+1] + n/2*power[n/2];

 }
 printf("%lld %lld\n",sum/n,(sum + sum1)/2/n);
 }
 return 0;
}

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com