島嶼渡假↘下殺$4900起新手>新婚族選績優龍頭股 正妹的東京自助旅行黃國昌嗆周祝瑛 教室一...
2014-02-17 16:38:11 人氣(40) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10547 - Hidden Truth in Recurrence

0
收藏
0
推薦

10547 - Hidd

Problem I
Hidden Truth in Recurrence
Time Limit: 1 second

You are given a recursive function, which has the following form:

Now, you have to find: , where

Input
There will be less than 1001 lines of inputs in the input file. Each line will contain three integers: k (0<k<1019), n (0<n<1019) and t (0<t<10). Input will be terminated by three zeros for the value of k, n and t. You must not process this case.

Output
For each line of input, output the value of x. The output should be in the format shown in the sample output.

Sample Input Sample Output
1234 1234 4
2323 99999999999 8
4 99999 9
888 888 8
0 0 0
Case #1: 736
Case #2: 39087387
Case #3: 494777344
Case #4: 91255296


Problemsetter: Tanbir Ahmed, special thanks to Monirul Hasan

#include <stdio.h>
typedef unsigned long long ULL;
ULL modpow(ULL x, ULL y, ULL mod) {
    ULL ret = 1;
    x %= mod;
    while(y) {
        if(y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    ULL k, n, t, a;
    int cases = 0;
    while(scanf("%llu %llu %llu", &k, &n, &t) == 3) {
        if(k + n + t == 0)
            break;
        for(a = 1; t; t--, a *= 10);
        printf("Case #%d: %llu\n", ++cases, modpow(k, n, a));
    }
    return 0;
}

10547Hidden Truth in Recurrence
台長:Morris
人氣(40) | ���應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][博弈] 11818 - Mouse & a Cheese
此分類上一篇:[UVA][剪枝] 10549 - Russian Dolls

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文