首页 > 代码库 > UVa 10093 - An Easy Problem!

UVa 10093 - An Easy Problem!

题目:给你一个62进制的数字R,找到最小的N使得R整除N-1。

分析:数论。从小到大枚举N即可,最小值为出现的字符中最大的值+1,最大值为62。

说明:注意数据可能很长,计算时保留余数即可。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

char list[63] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int  maps[128];

int  deal(char* buf)
{
	int min = 2;
	for (int i = 0 ; buf[i] ; ++ i)
		if (min <= maps[buf[i]])
			min = maps[buf[i]]+1;
	for (int i = min ; i < 63 ; ++ i) {
		int r = 0;
		for (int j = 0 ; buf[j] ; ++ j)
			r = (r*i+maps[buf[j]])%(i-1);
		if (r == 0) return i;
	}
	return -1;
}

int main()
{
	for (int i = 0 ; list[i] ; ++ i) 
		maps[list[i]] = i;
	char buf[10000];
	while (~scanf("%s",buf)) {
		int v = deal(buf);
		if (v != -1) printf("%d\n",v);
		else printf("such number is impossible!\n");
	}
    return 0;
}



UVa 10093 - An Easy Problem!