POJ 2115:
http://poj.org/problem?id=2115
A+Cx=B+(2^K)yの解(x,y)のうちxが非負で最小のものを求めればよい。これはユークリッドの互除法やるだけで求められるが、少し遠回りに書いたらREを起こしてえぇ…ってなりました。たぶんオーバーフロー起こしてましたね。シンプルに書いてAC。
ll extgcd(ll a, ll b, ll& x, ll& y) { if(b == 0) { x = 1; y = 0; return a; } ll res = extgcd(b, a % b, x, y); ll tx = x, ty = y; x = -ty; y = -tx - (a / b) * ty; return res; } int main() { while(true) { ll A, B, C, K; scanf("%lld%lld%lld%lld", &A, &B, &C, &K); if(A == 0 && B == 0 && C == 0 && K == 0) break; K = (1LL << K); ll x, y; ll G = extgcd(K, C, y, x); if((A - B) % G != 0) { printf("FOREVER\n"); continue; } K /= G; C /= G; x = x * ((A - B) / G); printf("%lld\n", (x % K + K) % K); } return 0; }
POJ 2345:
http://poj.org/problem?id=2345
いっけんムリそうですが、行列の形で書き下すと連立方程式解くだけでよいことがわかるので掃き出し法などすればよいです。
ムリそうだなぁと思ったらフローとか数学とかで考えるのがよさそう。
bool gauss_jordan(mat& A, vi& B) { int n = sz(B); rep(j, 0, n) { int at = -1; rep(i, j, n) { if(A[i][j] == 1) { at = i; break; } } if(at == -1) continue; swap(A[j], A[at]); swap(B[j], B[at]); rep(i, 0, n) { if(i == j || A[i][j] == 0) continue; B[i] = B[i] ^ B[j]; rep(k, 0, n) { A[i][k] = A[i][k] ^ A[j][k]; } } } rep(i, 0, n) { bool found = false; rep(j, 0, n) { if(A[i][j]) { found = true; break; } } if(!found && B[i]) return false; } return true; } int N; int main() { scanf("%d", &N); mat A(N, vi(N, 0)); rep(i, 0, N) { while(true) { int a; scanf("%d", &a); a--; if(a == -2) break; A[a][i] = 1; } } vi B(N, 1); if(gauss_jordan(A, B)) { vi ans; rep(i, 0, N) { if(B[i]) ans.pb(i + 1); } rep(i, 0, sz(ans)) { printf("%d%c", ans[i], i != sz(ans) - 1 ? ' ' : '\n'); } } else printf("No solution\n"); return 0; }