程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10692 - Huge Mods(數論)

uva 10692 - Huge Mods(數論)

編輯:C++入門知識

題目鏈接:uva 10692 - Huge Mods

題目大意:給出一個數的次方形式,就它模掉M的值。

解題思路:根據剩余系的性質,最後一定是行成周期的,所以就有ab=abmod(phi[M])+phi[M](phi[M]為M的歐拉函數),這樣就可以根據遞歸去求解。

#include 
#include 
#include 

const int maxn = 15;

int A[maxn], k;

int pow_mod (int a, int n, int M) {
    int ans = 1;

    while (n) {
        if (n&1)
            ans = ans * a % M;
        a = a * a % M;
        n /= 2;
    }
    return ans;
}

int euler_phi(int n) {
    int m = (int)sqrt(n+0.5);
    int ans = n;
    for (int i = 2; i <= m; i++) {
        if (n % i == 0) {
            ans = ans / i * (i-1);
            while (n%i==0)
                n /= i;
        }
    }

    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

int solve (int d, int M) {
    if (d == k - 1)
        return A[d]%M;

    int phi = euler_phi(M);
        int c = solve (d+1, phi) + phi;
    return pow_mod(A[d], c, M);
}

int main () {
    int cas = 1;
    char str[maxn];

    while (scanf("%s", str) == 1 && strcmp(str, "#")) {
        int M;
        sscanf(str, "%d", &M);
        scanf("%d", &k);
        for (int i = 0; i < k; i++)
            scanf("%d", &A[i]);

        printf("Case #%d: %d\n", cas++, solve(0, M));
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved