QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#818659#9248. An Easy Math ProblemZawos#TL 0ms3552kbC++20970b2024-12-18 02:37:492024-12-18 02:37:50

Judging History

This is the latest submission verdict.

  • [2024-12-18 02:37:50]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3552kb
  • [2024-12-18 02:37:49]
  • Submitted

answer

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

using ll = long long;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b) {
    return a == 0 ? b : gcd(b % a, a);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int q; cin >> q;
    while (q--) {
        ll n; cin >> n;
        set<pll> st;
        vector<ll> divs;
        for (ll d = 1; d * d <= n; d++) {
            if (n % d == 0) {
                divs.push_back(d);
                divs.push_back(n / d);
            }
        }

        for (auto d : divs) {
            for (ll p = 1; p * p <= d; p++) {
                if (d % p == 0) {
                    ll q = d / p;
                    ll g = gcd(p, q);

                    if (p > q)
                        st.insert({q / g, p / g});
                    else
                        st.insert({p / g, q / g});
                }
            }
        } 

        cout << st.size() << "\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

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: -100
Time Limit Exceeded

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:


result: