QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #138171 | #5503. Euclidean Algorithm | duckier | TL | 17821ms | 3624kb | C++14 | 3.2kb | 2023-08-11 05:21:12 | 2023-08-11 05:21:13 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int z, n, works[105][105];
int gcd(int x, int y) {
if (x > y) swap(x, y);
if (x == y) return x;
if (x == 0) return y;
return gcd(x, y % x);
}
bool solve(int x, int y) {
if (x > y) swap(x, y);
int g = gcd(x, y), c = y, counts = 1;
if (g == x || g == y) return true;
while (1) {
if (c == g) return true;
if (c <= 0)return false;
counts++;
c = counts * x - (counts - 1) * y;
}
return false;
}
int bash() {
int out = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (solve(i, j)) {
out++;
works[i][j]++;
}
}
}
return out;
}
signed main() {
//n = 2;
//for (; n <= 100; n++) {
// int ans = 0;
// //for (int i = 1; i <= n; i++) {
// // for (int j = 1; j <= n; j++) {
// // works[i][j] = 0;
// // }
// //}
// for (int r = 1; r <= n; r = n / (n / r) + 1) {
// int nr = n / r;
// for (int k = 1; k <= nr - 1; k = ((nr - 1) / ((nr - 1) / k)) + 1) {
// int pans = ans;
// int nx = (nr - 1) / ((nr - 1) / k);
// int nxr = n / (n / r);
// for (int i = k; i <= nx; i++) {
// for (int p = 2; p <= (nr - 1) / k; p++) {
// works[(i - 1) * p * r + r][i * p * r + r]++;
// if ((i - 1) * p * r + r == 2 && i * p * r + r == 3) {
// int asdf = 1;
// }
// }
// }
// ans += (nxr - r + 1) * ((nr - 1) / k - 1) * (nx - k + 1);
// if (pans > ans) {
// cout << "WTF234\n";
// }
// }
// }
// for (int k = 2; k <= n; k = n / (n / k) + 1) {
// int pans = ans;
// int nk = n / k;
// int nx = n / (n / k);
// ans += nk * (nx - k + 1);
// //for (int i = k; i <= nx; i++) {
// // for (int d = 1; d <= nk; d++) {
// // works[d * (i - 1)][d * i]++;
// // }
// //}
// if (pans > ans) {
// cout << "12312\n";
// }
// }
// if (ans != bash()) {
// cout << n << ' ' << ans << ' ' << bash() << '\n';
// }
// else {
// cout << "working :/'\n";
// }
//}
//return 0;
cin >> z;
while (z--) {
cin >> n;
int ans = 0;
//for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// works[i][j] = 0;
// }
//}
for (int r = 1; r <= n; r = n / (n / r) + 1) {
int nr = n / r;
for (int k = 1; k <= nr - 1; k = ((nr - 1) / ((nr - 1) / k)) + 1) {
int pans = ans;
int nx = (nr - 1) / ((nr - 1) / k);
int nxr = n / (n / r);
//for (int i = k; i <= nx; i++) {
// for (int p = 2; p <= (nr - 1) / k; p++) {
// works[(i - 1) * p * r + r][i * p * r + r]++;
// if ((i - 1) * p * r + r == 2 && i * p * r + r == 3) {
// int asdf = 1;
// }
// }
//}
ans += (nxr - r + 1) * ((nr - 1) / k - 1) * (nx - k + 1);
if (pans > ans) {
cout << "WTF234\n";
}
}
}
for (int k = 2; k <= n; k = n / (n / k) + 1) {
int pans = ans;
int nk = n / k;
int nx = n / (n / k);
ans += nk * (nx - k + 1);
//for (int i = k; i <= nx; i++) {
// for (int d = 1; d <= nk; d++) {
// works[d * (i - 1)][d * i]++;
// }
//}
//if (pans > ans) {
// cout << "12312\n";
//}
}
//bash();
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 17821ms
memory: 3452kb
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425
result:
ok 3 lines
Test #3:
score: -100
Time Limit Exceeded
input:
3 90076809172 100000000000 99913139559
output:
30192292781431 33790187414013