3978842_ac_63ms_600k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <map>
#include <stdio.h>
#include <ctype.h>
#include <algorithm>

using namespace std;

int base;

int change(char str[])
{
	int ret (0);

	for (int i = 0; str[i]; i++)
	{
		ret *= base;
		ret += isalpha(str[i]) ? (tolower(str[i]) - 'a' + 10) : (str[i] - '0');
	}
	return ret;
}

int h[100000];

int main()
{
	int n, cas;
	char num[100], den[100];
	int x, y, i;

	scanf("%d", &n);
	for (cas = 1; cas <= n; puts(""), cas++)
	{
		memset(h, 0, sizeof(h));
		printf("Scenario #%d:\n", cas);
		scanf("%d%s%s", &base, num, den);
		x = change(num);
		y = change(den);
		x %= y;
		i = 1;
		while (h[x] == 0)
		{
			h[x] = i++;
			x = x * base % y;
		}
		x == 0 ? puts("0") : printf("%d\n", i - h[x]);
	}
	return 0;
}