QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779730#9248. An Easy Math ProblemXiaoYang3TL 571ms5696kbC++231.0kb2024-11-24 21:26:572024-11-24 21:27:01

Judging History

This is the latest submission verdict.

  • [2024-11-24 21:27:01]
  • Judged
  • Verdict: TL
  • Time: 571ms
  • Memory: 5696kb
  • [2024-11-24 21:26:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
using pii = pair<ll, ll>;
ll n, m, k;
const ll P = 998244353;
map<int, int> mp;
void solve() {
    cin >> n;
    if (mp[n]) {
        cout << mp[n] << '\n';
        return;
    }
    vector<ll> v1;
    vector<ll> v2;
    // set<long double> se;
    for (int i = 1; i <= n / i; i++) {
        if (n % i == 0) {
            v1.push_back(i);
            v1.push_back(n / i);
        }
    }
    set<pii> se;
    for (auto x : v1) {
        for (auto y : v1) {
            if (y % x == 0) {
                ll xx = x, yy = y / x;
                if (xx < yy) {
                    swap(xx, yy);
                }
                ll d = __gcd(xx, yy);
                se.insert({xx / d, yy / d});
            }
        }
    }
    mp[n] = se.size();
    cout << se.size() << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1
2
2
3
2
5
2
4
3
5

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 10ms
memory: 5696kb

input:

2000
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
646969323...

output:

29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
...

result:

ok 2000 lines

Test #3:

score: 0
Accepted
time: 571ms
memory: 4084kb

input:

2000
1763047095
79735483
1016286871
2864801397
2327774116
2668010360
3469893354
3634459021
1613699068
781737219
574741575
2763134701
1458502604
1822260248
2281150332
2924219311
2493931196
3735904708
158802001
2006921221
729928782
1974841034
727412600
2873393292
1291087179
2741607663
1893408215
29827...

output:

14
5
2
5
23
95
68
14
8
68
203
14
23
32
38
41
8
8
14
2
608
41
158
338
23
41
14
5
14
41
14
203
41
14
17
446
5
53
59
878
2
14
365
203
14
203
2
122
32
95
41
41
5
23
14
41
5
5
14
122
23
203
608
23
41
122
2
14
95
2
68
41
203
14
230
41
68
23
50
14
32
14
8
5
5
5
68
68
122
293
473
5
41
41
14
2
14
14
5
2
122
...

result:

ok 2000 lines

Extra Test:

score: -3
Extra Test Failed : Time Limit Exceeded on 2

input:

2000
10000000000
9999999998
9999999996
9999999994
9999999992
9999999990
9999999988
9999999986
9999999984
9999999982
9999999980
9999999978
9999999976
9999999974
9999999972
9999999970
9999999968
9999999966
9999999964
9999999962
9999999960
9999999958
9999999956
9999999954
9999999952
9999999950
99999999...

output:


result: