結果

問題 No.3022 一元一次式 mod 1000000000
ユーザー GOTKAKO
提出日時 2025-02-14 22:16:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,103 bytes
コンパイル時間 1,990 ms
コンパイル使用メモリ 197,508 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-14 22:16:51
合計ジャッジ時間 3,048 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    long long Mod = 1'000'000'000;
    while(T--){
        long long N,M; cin >> N >> M;
        N %= Mod; M %= Mod;
        if(N == 0){
            if(M == 0) cout << 1 << "\n";
            else cout << "-1\n";
            continue;
        }
        long long g = gcd(Mod,N);
        if(M%g){cout << "-1\n"; continue;}
        if(M == 0){cout << Mod/g << "\n"; continue;}
        int time = 9;
        while(g%10 == 0) time--,g /= 10,N /= 10,M /= 10;

        vector<long long> OK = {0,1,2,3,4,5,6,7,8,9};
        long long mod = 1;
        for(int i=0; i<time; i++){
            mod *= 10;
            long long n = N%mod,m = M%mod;
            for(int k=0; k<10; k++){
                long long v = OK.at(k);
                if((n*v+m)%mod == 0){
                    OK.clear();
                    for(int l=0; l<10; l++) OK.push_back(v+mod*l); 
                    break;
                }
            }
        }
        cout << OK.at(0) << "\n";
    }
}
0