foj 1017 Playing with Calculator

http://acm.fzu.edu.cn/problem.php?pid=1017

枚举

设N的数位上的数为a, 则有

N = a*10^i + a*10^(i-1) + a*10^(i-2) + ... + a*10^1 + a*10^0

设c[j] = a*10^i + a*10^(i-1) + a*10^(i-2) + ... + a*10^1 + a*10^0 MOD k

则有c[j] = (c[j-1]*10 + a) MOD k

于是枚举a(1<=a<=9)与i(1<=i<k), 如果c[i]%k==0就找到了...

(参见:http://hi.baidu.com/iiywj/blog/item/abef42ca9c8434f752664fc5.html)

#include<iostream>
using namespace std;
int c[1000];
int main()
{
	int k,i,j;
	while(scanf("%d",&k)!=EOF)
	{
		c[0]=0;
		if(k==0||k==1)
		{
			printf("%d 1/n",k);
			continue;
		}
		for(i=1;i<10;i++)
		{
			for(j=1;j<k;j++)
			{
				c[j]=(c[j-1]*10+i)%k;
				if(!c[j])
				{
					printf("%d %d/n",i,j);
					break;
				}
			}
			if(j!=k)
				break;
		}
		if(i==10)
			printf("-1/n");
	}
	return 0;
}