3675463_ac_16ms_1260k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 58 行

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int a, b, c, s;
vector <int> num;
int mark[100000];

int main()
{
	int i, t;

	while (scanf("%d", &a) == 1 && a != 0)
	{
		scanf("%d%d%d", &b, &c, &s);
		memset(mark, 0, sizeof(mark));
		mark[s] = 1;
		num.clear();
		num.push_back(s);
		while (true)
		{
			t = (s * a + b) % c;
			if (mark[t] == 1)
				break;
			else
			{
				mark[t] = 1;
				s = t;
				num.push_back(t);
			}
		}
		int tmp = 1 << 15;
		for (i = 0; i < 16; i++, tmp >>= 1)
		{
			int cnt = 0;
			for (size_t j = 0; j < num.size(); j++)
			{
				if ((num.at(j) & tmp) != 0)
				{
					cnt++;
				}
			}
			if (cnt == 0)
				putchar('0');
			else
			{
				if (cnt == static_cast<int>(num.size()))
					putchar('1');
				else
					putchar('?');
			}
		}
		putchar('\n');
	}
	return 0;
}