C - 末三位

一：直接快速幂

#include<iostream>
using namespace std;

const int MOD = 10000;

int q_power(int a,int b){
    int res = 1;
    a %= MOD;
    while(b){
        if(b & 1) res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}

int main(){
    int n ;
    while(cin >> n){
        int ans = q_power(5, n);
        ans %= 1000;
        if(ans / 100 == 0) putchar('0');
        if(ans / 10  == 0) putchar('0');
        printf("%d\n",ans);
    }
    return 0;
}

二：循环节

$5^1\equiv5 (mod\ 1000)$

$5^2\equiv25 (mod\ 1000)$

$5^3\equiv125 (mod\ 1000)$

$5^4\equiv(5^1\times 5^3)(mod\ 1000)\equiv 625 (mod\ 1000)$

$5^5\equiv(5^2\times 5^3)(mod \ 1000)\equiv 125 (mod\ 1000)$

$5^6\equiv(5^2\times 5^4)(mod \ 1000)\equiv 625 (mod\ 1000)$

由上式中的 125 * 25 --> 125 我们可以得到当 n 为大于 1 的奇数时

$A_n = A_{n - 2} = …… = A_3 = 125$

同理偶数为 625

最后再处理一个 0 的时候就可以了

#include<iostream>
using namespace std;

int main(){
    int n ;
    while(cin >> n){
        if(n == 0) puts("001");
        else if(n == 1) puts("005");
        else if(n == 2) puts("025");
        else if(n & 1) puts("125");
        else puts("625");
    }
    return 0;
}