# 挑战程序竞赛系列（45）：4.1Polya 计数定理（1）

## Polya计数定理

NO，我们都知道，我跟你握是以我的视角，这和他跟我握本质上是一样的，所以我们在原来的基础上还需除以2，所以有答案：n * (n - 1) / 2

ans=1n∑k=0n−1mgcd(k,n)

ans = \frac{1}{n} \sum_{k = 0}^{n - 1} m^{gcd(k, n)}

## POJ 1286: Necklace of Beads

3×3n−12

3 \times 3^{\frac{n - 1}{2}}

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

String INPUT = "./data/judge/201709/P1286.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

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

public long pow(int a, int b){
long res = 1;
for (; b > 0; b >>= 1, a = a * a){
if ((b & 1) != 0){
res *= a;
}
}
return res;
}

static final int m = 3;

void solve() {
while (true){
int n = ni();
if (n == -1) break;

if (n == 0){
out.println(0);
continue;
}

long count = 0;
for (int i = 0; i < n; ++i){
count += pow(m, gcd(i, n));
}

if ((n & 1) != 0){ //奇数
count += n * pow(m, (n + 1) / 2);
}
else{
count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
}

out.println(count / (2 * n));
}
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

ans=1n∑d|nmd×{d出现的次数}

ans = \frac{1}{n}\sum_{d | n}m^d \times \{d出现的次数\}

ok，d出现的次数是什么呢？假设gcd(k, n) = d，且d一定是n的一个约束，k满足[0, n - 1)，所以满足k = dt的t的个数即为d出现的次数，于是有：

t∈[0,n/d)

t \in [0, n / d)

ans=1n∑d|nmd×ϕ(n/d)

ans = \frac{1}{n}\sum_{d | n}m^d \times \phi(n / d)

/******************约数枚举***********************/
public Set<Integer> prime_factors(int n){
Set<Integer> ans = new HashSet<Integer>();
for (int i = 1; i <= n / i; ++i){
if (n % i == 0){
}
}
return ans;
}

/*******************计算欧拉函数*******************/
public int phi(int n){
int res = n;
for (int i = 2; i <= n / i; ++i){
if (n % i == 0){
res = res / i * (i - 1);
for (; n % i == 0; n /= i);
}
}
if (n != 1){
res = res / n * (n - 1);
}
return res;
}

void solve() {
while (true){
int n = ni();
if (n == -1) break;

if (n == 0){
out.println(0);
continue;
}

Set<Integer> factors = prime_factors(n);

long count = 0;
for (int d : factors){
count += phi(n / d) * pow(m, d);
}

if ((n & 1) != 0){ //奇数
count += n * pow(m, (n + 1) / 2);
}
else{
count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
}

out.println(count / (2 * n));
}
}

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201709/P1286.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

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

public long pow(int a, int b){
long res = 1;
for (; b > 0; b >>= 1, a = a * a){
if ((b & 1) != 0){
res *= a;
}
}
return res;
}

static final int m = 3;

/******************约数枚举***********************/
public Set<Integer> divisor(int n){
Set<Integer> ans = new HashSet<Integer>();
for (int i = 1; i <= n / i; ++i){
if (n % i == 0){
}
}
return ans;
}

public Set<Integer> primes_factor(int n){
Set<Integer> ans = new HashSet<Integer>();

for (int i = 2; i <= n / i; ++i){
if (n % i == 0){
for (; n % i == 0; n /= i);
}
}

//针对素数的情况，直接返回一个素数
if (n != 1){
}

return ans;
}

void solve() {
while (true){
int n = ni();
if (n == -1) break;

if (n == 0){
out.println(0);
continue;
}

Set<Integer> factors = divisor(n);
Set<Integer> primes = primes_factor(n);

long count = 0;
for (int d : factors){

int phi = n / d;
for (int p : primes){
if ((n / d) % p == 0) phi = phi / p * (p - 1);
}
count += phi * pow(m, d);
}

if ((n & 1) != 0){ //奇数
count += n * pow(m, (n + 1) / 2);
}
else{
count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
}

out.println(count / (2 * n));
}
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

## POJ 2409: Let it Bead

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201709/P2409.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

public Set<Integer> primes_factor(int n){
Set<Integer> ans = new HashSet<Integer>();
for (int i = 2; i <= n / i; ++i){
if (n % i == 0){
for (; n % i == 0; n /= i);
}
}

if (n != 1){
}

return ans;
}

public Set<Integer> divisor(int n){
Set<Integer> ans = new HashSet<Integer>();
for (int i = 1; i <= n / i; ++i){
if (n % i == 0){
}
}
return ans;
}

public long pow(int a, int b){
long res = 1;
for (; b > 0; b >>= 1, a = a * a){
if ((b & 1) != 0){
res = res * a;
}
}
return res;
}

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

void solve() {
while (true){
int m = ni();
int n = ni();

if (m + n == 0) break;

if (n == 0) out.println(0);
else{
Set<Integer> factors = divisor(n);
Set<Integer> primes  = primes_factor(n);
long count = 0;
for (int d : factors){

int phi = n / d;
for (int p : primes){
if ((n / d) % p == 0) phi = phi / p * (p - 1);
}

count += phi * pow(m, d);
}

if ((n & 1) != 0){
count += n * pow(m, (n + 1) / 2);
}
else{
count += n / 2 * (pow(m, n / 2 + 1) + pow(m, n / 2));
}

out.println(count / (2 * n));
}
}
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

0 条评论

• ### POJ 刷题系列：2586. Y2K Accounting Bug

POJ 刷题系列：2586. Y2K Accounting Bug 传送门：2586. Y2K Accounting Bug 题意： 有一个公司由于某个病毒使...

• ### 挑战程序竞赛系列（42）：4.1模运算的世界（4）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### POJ 刷题系列：3295. Tautology

题意： 给出二元变量 p，q，r，s，t以及运算符K，A，N，E，C，求所给运算符和变量的集合是否符合永真，若永真输出tautology，否则输出not。 思...

• ### 面试算法题

题目来源于牛客网：https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中，每一行都按...

• ### POJ 刷题系列：2586. Y2K Accounting Bug

POJ 刷题系列：2586. Y2K Accounting Bug 传送门：2586. Y2K Accounting Bug 题意： 有一个公司由于某个病毒使...

• ### POJ 刷题系列：3295. Tautology

题意： 给出二元变量 p，q，r，s，t以及运算符K，A，N，E，C，求所给运算符和变量的集合是否符合永真，若永真输出tautology，否则输出not。 思...

• ### 挑战程序竞赛系列（42）：4.1模运算的世界（4）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### POJ 刷题系列：2159. Ancient Cipher

POJ 刷题系列：2159. Ancient Cipher 传送门：POJ 2159. Ancient Cipher 题意： 给定两个长度相等的字符串a, b...

• ### POJ 刷题系列：1936. All in All

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/...

• ### POJ 刷题系列：2262. Goldbach's Conjecture

POJ 刷题系列：2262. Goldbach’s Conjecture 传送门：POJ 2262. Goldbach’s Conjecture 题意： 给定...