24h購物| | PChome| 登入
2012-12-18 22:59:06| 人氣5,004| 回應0 | 上一篇 | 下一篇

[UVA][cycle] 10162 - Last Digit

推薦 0 收藏 0 轉貼0 訂閱站台

10162 - Last Digit


 Problem B.Last Digit 

Background

  Give you a integer number N (1<=n<=2*10100). Please compute

            S=11+22+33+…+NN

  Give the last digit of S to me.

 

 

Input

  Input file consists of several Ns, each N a line. It is ended with N=0.

 

 

Output

  For each N give a line containing only one digit, which is the last digit of S.

 

 

Sample Input

1

2

3

0

 

 

Sample Output

1

5

2

就以 N^N 尾數循環是 1~20 一次 之後每 20 輪一次。
那答案則是 1~100 一次 之後每 100 輪一次。


#include <stdio.h>
#include <string.h>
long long mpow(long long x, long long y, long long mod) {
    if(y == 0)  return 1;
    if(y&1)
        return x*mpow(x*x%mod, y/2, mod)%mod;
    return mpow(x*x%mod, y/2, mod);
}
int cycle[101];
void findcycle() {
    int i, j;
    for(i = 0; i < 10; i++) {
        for(j = i*10+1; j <= i*10+10; j++) {
            cycle[j] = cycle[j-1]+mpow(j, j, 10);
            //printf("%lld ", mpow(j, j, 10));
        }
    }
}
int main() {
    findcycle();
    char s[200];
    while(scanf("%s", s) == 1) {
        if(s[0] == '0' && s[1] == '\0')
            break;
        int n;
        if(strlen(s) > 5)
            sscanf(s+strlen(s)-5, "%d", &n);
        else
            sscanf(s, "%d", &n);
        printf("%d\n", (cycle[n%100])%10);
    }
    return 0;
}

我要檢舉
#10162#Last Digit
台長： Morris

您可能對以下文章有興趣

人氣(5,004) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][遞迴] 12041 - BFS (Binary Fibonacci String)
此分類上一篇:[UVA][greedy+dp] 711 - Dividing up

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文