QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #839752 | #7230. Fraction Factory | liyujia | WA | 1ms | 5520kb | C++17 | 949b | 2025-01-02 08:51:44 | 2025-01-02 08:51:46 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define _ (__int128)
using namespace std;
const int N = 500005;
int n, m, q, mod, a[N], b[N];
int exgcd(int x, int y, int &A, int &B){
if(!y) return A = 1, B = 0, x;
int ans = exgcd(y, x % y, B, A);
B -= x / y * A; return ans;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
int t = __gcd(a[i], b[j]);
a[i] /= t, b[j] /= t;
}
cin >> q;
while(q--){
cin >> mod;
int p1 = 1, p2 = 1;
for(int i = 1; i <= n; i++) p1 = _(1) * p1 * a[i] % mod;
for(int i = 1; i <= m; i++) p2 = _(1) * p2 * b[i] % mod;
if(!p2 || __gcd(p2, mod) != 1) cout << "DIVISION BY ZERO\n";
else{
int A, B; exgcd(p2, mod, A, B);
cout << (int)(_(1) * p1 * A % mod) << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5520kb
input:
3 2 8 11 14 9 12 4 8 9 10 11
output:
4 DIVISION BY ZERO 4 0
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5520kb
input:
2 2 1 2 4 3 10 5 7 11 13 17 19 23 29 31 37
output:
1 -1 2 -2 3 -3 4 5 -5 -6
result:
wrong answer 2nd lines differ - expected: '6', found: '-1'