poj 1152数学問題(進数ビット)

题意:あなたに1つのN进法の整数Rをあげて、题目はRがN-1によって整除することができることを保证して、あなたに条件の最小のNを満たすことを求めさせます.
分析:多くの大牛が水の問題を感じているのを見て、しかしやはり数論で証明しなければならなくて、自分で証明することができなくて、牛人の証明を見てやっと水が落ちることができます~~
数論の模演算証明:
入力がabcdであるとし,その解がn進法であると仮定すると,
(a*n*n*n + b*n*n + c*n + d)%(n-1)=0
 

  ：( (a*n*n*n)%(n-1)+ (b*n*n)%(n-1)+ (c*n)%(n-1)+d  )%(n-1)=0
  ：((a* (n%(n-1)) *(n%(n-1)) *(n%(n-1))) + (b* (n%(n-1)) *(n%(n-1)))  + (c* (n%(n-1)  +  d ) %(n-1)=0
  : (a*1*1*1 + b*1*1 + c*1 + d) % (n-1)=0
  ：(a+b+c+d)%(n-1)=0
  ，    ，             ％（n-1)  0；

       ：0...9...A...Z...a...z （     ，A=10, a=37）         ；

        The largest size of the input file will be 32KB       30001  ~

#include<iostream>
#include<string>
using namespace std;

char str[35000];
int len, n;

int main()
{
	int i,j;
	int sum,min,s;
	while(scanf("%s",&str) != EOF)
	{
		n = -5;
		sum = 0;
		len = strlen(str);
		for(i=0; i<len; i++)
		{
			if(str[i]>='0' && str[i]<='9')
				s = str[i] - '0';			//0 ~ 9
			if(str[i]>='A' && str[i]<='Z')
				s = str[i] - 'A' + 10;		//A=10 ~ Z=36             10
			if(str[i]>='a' && str[i]<='z')
				s = str[i] - 'a' + 36;		//a=37 ~ z= 63      36；
			sum += s;
			if(s > n)	//         ，          (N>=n);
				n = s;
		}
		if(n==0)
		{
			printf("2/n");
			continue;
		}
		min = 100;
		for(i=n; i<=62; i++)	// n    
		{
			if(sum % i == 0)
			{
				min = i;
				break;
			}
		}
		if(min <= 61)
			printf("%d/n",min+1);   //       sum%(n-1),       +1；
		else
			printf("such number is impossible!/n");
	}
	return 0;
}