Submission #374286

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

typedef unsigned long long ull;

ull rev(ull x, int n) {
	long long y = 0;
	rep(i, n) if(x >> i & 1)
		y |= 1LL << (n-1-i);
	return y;
}
ull step(ull a, ull b, int n) {
	a <<= 1;
	if(a >> n & 1)
		a ^= (1LL << n) | b;
	return a;
}

static int bsr(unsigned long long x) {
#if defined(__GNUC__)
	return 63 - __builtin_clzll(x);
#else
	int r = 0;
	if(x & 0xffffffff00000000ULL) x >>= 32, r += 32;
	if(x &         0xffff0000U  ) x >>= 16, r += 16;
	if(x &             0xff00U  ) x >>= 8,  r += 8;
	if(x &               0xf0U  ) x >>= 4,  r += 4;
	if(x &                0xcU  ) x >>= 2,  r += 2;
	if(x &                0x2U  )           r += 1;
	return r;
#endif
}
int highestOneIdx(ull x) {
	return bsr(x);
}

ull divide(ull a, ull b) {
	int db = highestOneIdx(b), da;
	ull q = 0;
	while(db <= (da = highestOneIdx(a))) {
		if(a == 0) break;
		a ^= b << (da - db);
		q ^= 1ULL << (da - db);
	}
	return q;
}
ull multiply(ull a, ull b) {
	ull t = 0;
	while(b) {
		if(b & 1) t ^= a;
		b >>= 1;
		a <<= 1;
	}
	return t;
}
ull mulmod(ull a, ull b, ull c, ull h) {
	ull t = 0;
	while(b) {
		if(b & 1) t ^= a;
		b >>= 1;
		ull s = a & h;
		a <<= 1;
		if(s) a ^= c;
	}
	return t;
}
ull egcd(ull u, ull v, ull &iu, ull &iv) {
	ull u1 = 1, u2 = 0;
	ull v1 = 0, v3 = v;
	ull u3 = u, v2 = 1;
	while(v3 != 0) {
		ull q = divide(u3, v3);

		ull t1 = u1 ^ multiply(v1, q);
		u1 = v1, v1 = t1;

		ull t3 = u3 ^ multiply(v3, q);
		u3 = v3, v3 = t3;

		ull t2 = u2 ^ multiply(v2, q);
		u2 = v2, v2 = t2;
	}
	iu = u1, iv = u2;
	return u3;
}
ull gcd(ull u, ull v) {
	ull a, b;
	ull g = egcd(u, v, a, b);
	assert((multiply(a, u) ^ multiply(b, v)) == g);
	return g;
}

ull inverse(ull a, ull c) {
	ull i, t;
	ull g = egcd(a, c, i, t);
	if(g != 1) i = 0;
	return i;
}

long long solve(ll AA, ll BB, ll XX) {
	int n = 0;
	while((max(max(AA, BB), XX) >> n) != 0) ++ n;
	ull a = rev(AA, n), b = rev(BB, n), x = rev(XX, n);
	//(Z/2Z)[X]/(X^n+b)上のdiscrete logarithm (bを多項式として見る)
	const int First = 40;
	long long ans = -1;
	if(a == x) {
		ans = 0;
	}else {
		rep(i, First) {
			a = step(a, b, n);
			if(a == x) {
				ans = i + 1;
				break;
			}
		}
	}
	if(ans != -1) {
		return ans;
	}
	if(b == 0) {
		return -1;
	}
	assert((a >> n) == 0 && (b >> n) == 0);
	assert(n != 0);
	if(n == 1) {
		assert(b == 1);
		return -1;
	}
	ull g = gcd(b | (1ULL << n), a);
	ull aa = divide(a, g);
	ull bb = divide(b | (1ULL << n), g);
	ull xx = divide(x, g);

	if(multiply(xx, g) != x) {
		return -1;
	}

	int m = 0;
	while((bb >> m) != 1) ++ m;
	ull h = 1ULL << (m-1);

	if((xx >> m) != 0) {
		return -1;
	}

	ull iaa = inverse(aa, bb);
	assert(iaa != 0);
	ull z = mulmod(xx, iaa, bb, h);

	int S = 1 << ((m + 1) / 2);
	vector<pair<ull,int> > table(S);
	ull p = 1;
	rep(i, S) {
		table[i] = mp(p, i);
		p = mulmod(p, 2, bb, h);
	}
	sort(all(table));
	ull c = 1;
	rep(i, S)
		c = mulmod(c, 2, bb, h);
	c = inverse(c, bb);
	assert(c != 0);
	int T = (int)(((1LL << m) + S - 1) / S);
	ull y = z;
	rep(i, T) {
		vector<pair<ull,int> >::const_iterator it =
			lower_bound(table.begin(), table.end(), make_pair(y, -1));
		if(it != table.end() && it->first == y) {
			ans = First + (ll)i * S + it->second;
			break;
		}
		y = mulmod(y, c, bb, h);
	}
	return ans;
}

int main() {
	/*
	while(1) {
		int A = rand() % 1000, B = rand() % 1000, X = rand() % 1000;
		ll ans = solve(A, B, X);
		int naiveans = -1;
		{	int a = A;
			rep(i, 1500) {
				if(a == X) {
					naiveans = i;
					break;
				}
				a = (a / 2) ^ (a % 2 * B);
			}
		}
		if(ans != naiveans) {
			cout << A << ", " << B << ", " <<X << ": " << ans << " != " << naiveans << endl;
		}
	}
	*/
	long long AA, BB, XX;
	while(cin >> AA >> BB >> XX) {
		long long ans = solve(AA, BB, XX);
		cout << ans << endl;
	}
	return 0;
}

Submission Info

Judge Result