QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662277#9248. An Easy Math Problem123BVNRE 419ms7584kbC++231.9kb2024-10-20 22:30:352024-10-20 22:30:39

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-20 22:30:39]
  • Judged
  • Verdict: RE
  • Time: 419ms
  • Memory: 7584kb
  • [2024-10-20 22:30:35]
  • Submitted

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define llu unsigned long long
#define endl "\n"
#define inf 0x3f3f3f3f
#define debug cout << "****************" << endl
#define bit(x) (1LL << x)
using namespace std;

typedef pair<int, int> PII;

const int N = 5e5 + 7;

vector<int> p3(100);

void solve()
{
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        vector<int> st1;
        vector<int> mp(N);
        int n;
        cin >> n;
        for (int j = 2; j * j <= n; j++)
        {
            while (n % j == 0)
            {
                n /= j;
                if (!mp[j])
                    st1.push_back(j);
                mp[j]++;
            }
        }
        if (n > 1)
        {
            if (!mp[n])
                st1.push_back(n);
            mp[n]++;
        }

        int sum = 1;
        for (auto x : st1)
        {
            int y = mp[x];
            sum *= y + 1;
        }
        int ans = 0;
        int cnt = st1.size();
        for (int j = 1; j < bit(cnt); j++) // 6e4
        {
            int res = 1;
            int res1 = 1;
            int res2 = 1;
            vector<int> st2(100);
            int ok = 1;
            int x = j;
            int now = 0;
            while (x)
            {
                st2[now] = x % 2;
                x /= 2;
                now++;
            }
            for (int k = 0; k < st1.size(); k++)
            {
                if (st2[k] == 0)
                    res1 *= (mp[st1[k]] + 1);
                else
                    res2 *= mp[st1[k]];
            }
            res = (res1 - 1) * res2;
            ans += res;
        }
        cout << ans / 2 + sum << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    int x = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7584kb

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: 419ms
memory: 7532kb

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: -100
Runtime Error

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:


result: