Description

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 atIBM) 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 arickshaw (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 interestingnecklace 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 differentnecklace/bracelet can be made with a certain construction set. You are requested to help him again. The following things are true for anecklace/bracelet construction set.

a)      All necklace/bracelet construction sets has a frame, which hasN 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 istN (t multiplied by N), of which exactlyN 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 tobracelets. A bracelet is a necklace that can be turned over (A junior programmer in Bangladesh says that wrist watch is anecklace (Boys!!! Don’t mind :-))). So for a bracelet 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 integersN(0<N<51) and t(0<t<11) as described in the problem statement. Also note that within this input range inputs will be such that no final result will exceed11 digits. Input is terminated by end of file.  

Output

For each line of input produce one line of output which contains two round numbersNN 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

题意：项链和手镯都是由若干个珠子串成的环形首饰，区别在于手镯可以翻转和旋转，但是项链只能旋转

思路：等价类计数问题，利用Polya定理，一共有两种置换，旋转和翻转，旋转推出如果按i颗珠子的间隔旋转，则这个循环有n/gcd(n, i)个元素，一共有gcd(i, n)个循环，这些置换的不动点总数有a = t^gcd(i, n){0 <= i <= n-1}； 翻转的话，分奇偶性，根据对称轴得到奇数的时候 b = n* t^(n+1)/2， 偶数的时候b =n/2*(t^(n/2+1) + t^(n/2))

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 105;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}

int main() {
	int n, t;
	while (scanf("%d%d", &n, &t) != EOF && n) {
		ll pow[maxn];
		pow[0] = 1;
		for (int i = 1; i <= n; i++)
			pow[i] = pow[i-1] * t;
		ll a = 0;
		for (int i = 0; i < n; i++)
			a += pow[gcd(i, n)];
		ll b = 0;
		if (n % 2 == 1)
			b = n * pow[(n+1)/2];
		else b = n / 2 * (pow[n/2+1] + pow[n/2]);
		printf("%lld %lld\n", a/n, (a+b)/2/n);
	}
	return 0;
}

UVA - 10294 Arif in Dhaka (First Love Part 2) （Polya定理）