全体公開 > 合同練習会 > 20130323 > K 等式

問題の概要

x, y, zを変数として持ち, 演算は+と*のみであるようなものが左辺に現れ, 右辺は100以下の正整数であるような式が与えられる.
これを満足する正整数x, y, zの組み合わせの総数を答えよ.

実装の方針, 注意点

...

x, y, zをそれぞれ1から100まで変化させ, 全パターン調べる.
但し, 式に出てこない変数は固定する.

100^3回もstringからパースすると重いので, 各項について, 係数と, 変数のべきを先に調べておく.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx+1=1 に対する答えが 0 である事に注意せよ.
intで計算していると, オーバーフローし, xが2の倍数の時, 等号が成立してしまう.
大きくなってきたらダメと判定するか, double等で判定する必要がある.

ソースコード

Not verified

...

bool inRange(int a, int x, int b){
    return a <= x && x < b;
}
bool solve(){
    string s;
    getline(cin, s);
    if(s[0] == '.') return false;
 
    vvi term(3, vi(1)); // 各変数の i 項目のべき
    vi c(1);            // i 項目の係数
    int use[3] = {};
    int n = 0;
    int ans = 0;
    for(int p = 0; ; ++p){
        if(s[p] == '+' || s[p] == '='){
            if(!c[n]) c[n] = 1;
            ++n;
            if(s[p] == '+'){
                rep(i, 3) term[i].pb(0);
                c.pb(0);
            }else{
                ++p;
                while(p < sz(s)){
                    ans *= 10;
                    ans += s[p] - '0';
                    ++p;
                }
                break;
            }
        }else if(s[p] == '='){
        }else if(inRange('0', s[p], '9'+1)){
            c[n] *= 10;
            c[n] += s[p]-'0';
        }else{
            ++term[s[p]-'x'][n];
            use[s[p]-'x'] = true;
        }
    }
 
    int res = 0;
    int xyz[3];
    for(xyz[0] = 1; xyz[0] <= (use[0] ? 100 : 1); ++xyz[0]){
        for(xyz[1] = 1; xyz[1] <= (use[1] ? 100 : 1); ++xyz[1]){
            for(xyz[2] = 1; xyz[2] <= (use[2] ? 100 : 1); ++xyz[2]){
                double s = 0;
                rep(i, n){
                    double t = c[i];
                    rep(j, 3) rep(k, term[j][i]) t *= xyz[j];
                    s += t;
                }
                if(abs(s - ans) < 0.5) ++res;
            }
        }
    }
    cout << res << endl;
 
    return true;
}
 

編集

---