AOJ 0110 Alphametic
覆面算 | Aizu Online Judge
概要
A + B = C
という形式で式が与えられる。式の長さは 126 以下である。
与えられる数値にはひとつ以上の X が含まれている。
X は 0 以上 9 以下の整数である。
X に当てはまる整数を求めよ。当てはまる整数がない場合は NA を出力せよ。
実装
X に当てはまる数値を全探索する。
多倍長整数でなければオーバーフローする。
ではどうするか。
modを使うのである。
この嘘解法を落とすケースはあるようで、 mod 10^9 + 7 と mod 10^9 + 9 ではWA。
よくわからない大きな素数でmodを取るとACする
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; //const int INF = 1e8; using namespace std; const long long M = 67280421310721LL; vector<string> split(string in, char sp = ' '){ vector<string> ret; stringstream ss(in); string s; while(getline(ss, s, sp)){ ret.emplace_back(s); } return ret; } void modmod(vector<string> sp, int start){ range(i,start,10){ vector<long long> a(3,0); rep(j,3){ for(auto c : sp[j]){ (a[j] *= 10) %= M; if(c == 'X') a[j] += i; else a[j] += c - '0'; } } if((a[0] + a[1]) % M == a[2] % M){ cout << i << endl; return; } } cout << "NA" << endl; return; } int main(){ string s; while(cin >> s){ rep(i,s.size()) if(s[i] == '+') s[i] = '='; vector<string> sp = split(s, '='); int start = 0; for(auto& i : sp) if(i.front() == 'X' and i.size() > 1) start = 1; modmod(sp, start); } }