POJ 1455 Crazy Tea Party：循環排列計數

問題描述

n 個人圍圓桌就座，每人有一杯茶。規則：每人將茶遞給左邊第 k 個人（k 固定）。經過若干輪後，要求每人手中的茶杯都不相同（即排列無不动點）。求滿足條件的 k 個數（1 ≤ k < n）。

數學分析

第 i 輪後，第 j 位人的茶杯來自 (j - i*k) mod n。要使最終無人拿到原茶杯，需對所有 j，j ≠ (j - t*k) mod n 對某些 t 成立，即 t*k ≢ 0 (mod n) 對所有 1≤tk 與 n 互質（gcd(k,n)=1）。

答案

滿足條件的 k 個數即為 φ(n)（歐拉函數）。

代碼實現

#include 
using namespace std;

int phi(int n) {
    int res = n;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res = res / i * (i - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int main() {
    int n;
    while (cin >> n) {
        cout << phi(n) << endl;
    }
    return 0;
}

複雜度

• 分解質因數 O(√n)，極快。

總結

本題本質是求與 n 互質的數的個數，即歐拉函數 φ(n)。關鍵在於將「茶杯傳遞」建模為模 n 乘法群，識別出無不动點排列的條件正是生成元（或更廣義的互質條件）。