結果
問題 | No.3022 一元一次式 mod 1000000000 |
ユーザー |
|
提出日時 | 2025-02-14 22:00:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,054 bytes |
コンパイル時間 | 5,966 ms |
コンパイル使用メモリ | 334,248 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-02-14 22:05:18 |
合計ジャッジ時間 | 7,609 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 1 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>// using mint = atcoder::static_modint<998244353>;// //using mint = atcoder::static_modint<1000000007>;using namespace std;using namespace atcoder;using ld = long double;using ll = long long;#define mp(a,b) make_pair(a,b)#define rep(i,s,n) for(int i=s; i<(int)n; i++)const vector<int> dx{1,0,-1,0},dy{0,1,0,-1};void solve(){ll mod=1e9;ll n,m;cin >> n >> m;n%=mod;m=(mod-m%mod)%mod;if(n==0){if(m==0)cout << 1 << "\n";else cout << -1 << "\n";return;}ll ord=mod*100;while(n%2==0){n/=2;mod/=2;if(m%2!=0){cout << -1 << "\n";return;}m/=2;}while(n%5==0){n/=5;mod/=5;if(m%5!=0){cout << -1 << "\n";return;}m/=5;}ll inv_n=pow_mod(n,ord-1,mod);ll ans=m*inv_n%mod;if(ans==0)ans+=mod;cout << ans << "\n";}int main(){int T;cin >> T;rep(i,0,T)solve();}