首页 > 代码库 > uva 10162 - Last Digit(数论)

uva 10162 - Last Digit(数论)

题目链接:uva 10162 - Last Digit

题目大意:给定n,求s的个位的数值是多少。

解题思路:对于ii,重复周期为20,这样就有

  • 1 4 7 6 5 6 3 6 9 0
  • 1 6 3 6 5 6 7 4 9 0
    但是这个周期的值是不为0的,总的话是100为一个大周期。
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxt = 100;
const int maxn = 205;

int t[maxt];
char s[maxn];

int pow_mod(int a, int n) {
    int ans = 1;
    while (n) {
        if (n&1)
            ans = ans * a % 10;
        n /= 2;
        a = a * a % 10;
    }
    return ans;
}

void init () {
    t[0] = 0;
    for (int i = 1; i <= maxt; i++) {
        t[i] = (t[i-1] + pow_mod(i%10, i))%10;
    }
}

int main () {
    init();
    while (scanf("%s", s) == 1 && strcmp(s, "0")) {
        int len = strlen(s);
        int ans = 0;
        for (int i = 0; i < len; i++)
            ans = (ans * 10 + s[i] - ‘0‘)%maxt;
        printf("%d\n", t[ans]);
    }
    return 0;
}