余数 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
", x);
			else	printf ("%d
", x);
		}
	}

	return 0;
}