QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656130#9248. An Easy Math ProblemFiatiustitia#TL 1ms3888kbC++202.2kb2024-10-19 11:28:332024-10-19 11:28:34

Judging History

This is the latest submission verdict.

  • [2024-10-31 22:36:43]
  • hack成功,自动添加数据
  • (/hack/1098)
  • [2024-10-31 22:13:58]
  • hack成功,自动添加数据
  • (/hack/1096)
  • [2024-10-31 22:00:43]
  • hack成功,自动添加数据
  • (/hack/1095)
  • [2024-10-19 11:28:34]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3888kb
  • [2024-10-19 11:28:33]
  • Submitted

answer

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

vector<int> minp, prime;
void sieve(int n)
{
    minp.resize(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (!minp[i])
        {
            minp[i] = i;
            prime.push_back(i);
        }
        for (auto p : prime)
        {
            if (p * i > n)
                break;
            minp[i * p] = p;
            if (i % p == 0)
                break;
        }
    }
}
vector<pair<long long, int>> p;
vector<int> q;
void dfs(int u, long long pre)
{
    if (u == p.size())
    {
        q.push_back(pre);
        return;
    }
    for (int i = 0; i <= p[u].second; i++)
    {
        dfs(u + 1, pre);
        pre *= p[u].first;
        // cout<<pre<<'\n';
    }
}
void solve()
{
    long long n;
    cin >> n;
  //  n = 1e10;
    long long tmp = n;
    p.clear(), q.clear();
    for (auto i : prime)
    {
        if (i > n / i)
            break;
        if (n % i == 0)
        {
            int cnt = 0;
            while (n % i == 0)
            {
                cnt++;
                n /= i;
            }
            p.push_back(make_pair(i, cnt));
        }
    }
    if (n != 1)
    {
        p.push_back(make_pair(n, 1));
    }
    dfs(0, 1);
    sort(q.begin(), q.end());
    const int m = q.size();
    // cout << q.size() << '\n';
    // set<long long> se;
    vector<int64_t> t;
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j <= i;j++)
        {
            t.push_back(tmp / q[i] * q[j]);
        }
    }
    sort(t.begin(),t.end());
    t.resize(unique(t.begin(),t.end()) - t.begin());

    // for (int i = 0; i < q.size(); i++)
    // {
    //     // cout << q[i] << '\n';
    //     for (int j = 0; j <= i; j++)
    //     {
    //         se.insert(1ll * tmp / q[i] * q[j]);
    //     }
    // }
    cout << t.size() << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    auto _ = clock();
#endif
    sieve(1e5 + 7);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
#ifdef LOCAL
    cerr << clock() - _ << '\n';
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: