3978668_wa.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;
}

//map <int, int> h;
int h[100000];

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

	//freopen("sin", "r", stdin);
	scanf("%d", &n);
	for (cas = 1; cas <= n; puts(""), cas++)
	{
		//h.clear();
		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;
		h[x] = 1;
		for (i = 2; x != 0; i++)
		{
			while (x < y)
			{
				x *= base;
			}
			x %= y;
			if (h[x] != 0)
			{
				printf("%d\n", i - h[x]);
				break;
			}
			h[x] = i;
		}
		x == 0 && puts("0");
	}
	return 0;
}