余数 2015广工校赛 C 魔幻任务

题目传送门

题意:问n位最小能整除47的数字

分析:打表发现前面都是100000…,后两位就是100000%47后到47的距离,就是快速幂求1000000%47的值,47-它就是后两位

#include <bits/stdc++.h>
using namespace std;const int A = 47;int pow_mod(int x, int n, int p){
int ret = 1;
while (n){
if (n & 1)ret = 1ll * ret * x % p;
x = 1ll * x * x % p;
n >>= 1;
}
return ret;
}int run(int n){
return A - pow_mod (10, n, A);
}int main(void){
int T;scanf ("%d", &T);
while (T--){
int n;scanf ("%d", &n);
if (n <= 0)puts ("-1");
else if (n == 1)puts ("0");
else if (n == 2)puts ("47");
else{
printf ("1");
for (int i=1; i<=n-3; ++i)printf ("0");
int x = run (n - 1);
if (x < 10)printf ("0%d\n", x);
elseprintf ("%d\n", x);
}
}return 0;
}