UVA 11255 Necklace
12051 ワード
UVA_11255
burnside引数を適用するには,各置換に対して不動スキームの種数を求めることが重要である.
burnside引数を適用するには,各置換に対して不動スキームの種数を求めることが重要である.
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static int MAXD = 50;
static Scanner cin = new Scanner(System.in);
static int N, P, pn;
static int[] a = new int[5], b = new int[5], prime = new int[MAXD], p = new int[MAXD];
static boolean[] isprime = new boolean[MAXD];
static BigInteger[] fac = new BigInteger[MAXD];
static BigInteger ans;
public static void main(String[] args) {
prepare();
int t = cin.nextInt();
while(t != 0)
{
-- t;
init();
solve();
}
}
static void prepare()
{
int i, j, k = 40;
fac[0] = fac[1] = new BigInteger("1");
for(i = 2; i <= k; i ++)
fac[i] = fac[i - 1].multiply(BigInteger.valueOf(i));
for(i = 0; i <= k; i ++)
isprime[i] = true;
P = 0;
for(i = 2; i <= k; i ++)
if(isprime[i])
{
prime[P ++] = i;
for(j = i * i; j <= k; j += i)
isprime[i] = false;
}
}
static void init()
{
int i;
N = 0;
for(i = 0; i < 3; i ++)
{
a[i] = cin.nextInt();
N += a[i];
}
divide(N);
}
static void divide(int n)
{
int i;
pn = 0;
for(i = 0; i < P && prime[i] * prime[i] <= n; i ++)
if(n % prime[i] == 0)
{
p[pn ++] = prime[i];
while(n % prime[i] == 0)
n /= prime[i];
}
if(n > 1)
p[pn ++] = n;
}
static int euler(int n)
{
int i, ans = n;
for(i = 0; i < pn; i ++)
if(n % p[i] == 0)
ans = ans / p[i] * (p[i] - 1);
return ans;
}
static void solve()
{
ans = new BigInteger("0");
dfs(0, 1, N);
if(N % 2 == 1)
{
for(int i = 0; i < 3; i ++)
{
for(int j = 0; j < 3; j ++)
b[j] = a[j];
-- b[i];
if(b[i] < 0)
continue;
ans = ans.add(calculate(2).multiply(BigInteger.valueOf(N)));
}
}
else
{
for(int i = 0; i < 3; i ++)
b[i] = a[i];
ans = ans.add(calculate(2).multiply(BigInteger.valueOf(N / 2)));
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
{
for(int k = 0; k < 3; k ++)
b[k] = a[k];
-- b[i];
-- b[j];
if(b[i] < 0 || b[j] < 0)
continue;
ans = ans.add(calculate(2).multiply(BigInteger.valueOf(N / 2)));
}
}
ans = ans.divide(BigInteger.valueOf(2 * N));
System.out.println(ans);
}
static BigInteger calculate(int m)
{
int i, n = 0;
BigInteger ans = new BigInteger("1");
for(i = 0; i < 3; i ++)
{
if(b[i] % m != 0)
return BigInteger.ZERO;
b[i] /= m;
n += b[i];
}
for(i = 0; i < 3; i ++)
{
ans = ans.multiply(comb(n, b[i]));
n -= b[i];
}
return ans;
}
static void dfs(int cur, int v, int x)
{
int i, cnt = 0, t = 1;
if(cur == pn)
{
for(i = 0; i < 3; i ++)
b[i] = a[i];
ans = ans.add(calculate(N / v).multiply(BigInteger.valueOf(euler(N / v))));
return ;
}
while(x % p[cur] == 0)
{
++ cnt;
x /= p[cur];
}
for(i = 0; i <= cnt; i ++)
{
dfs(cur + 1, v * t, x);
t *= p[cur];
}
}
static BigInteger comb(int n, int m)
{
return fac[n].divide(fac[m]).divide(fac[n - m]);
}
}