QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1096#696154#9248. An Easy Math ProblemCore_65536Core_65536Success!2024-10-31 22:13:452024-10-31 22:13:45

详细

Extra Test:

Time Limit Exceeded

input:

2000
10000000000
9999999800
9999999600
9999999400
9999999200
9999999000
9999998800
9999998600
9999998400
9999998200
9999998000
9999997800
9999997600
9999997400
9999997200
9999997000
9999996800
9999996600
9999996400
9999996200
9999996000
9999995800
9999995600
9999995400
9999995200
9999995000
99999948...

output:

221
473
608
158
83
1103
203
158
13163
53
95
473
248
263
1013
221
113
2363
608
158
1040
473
203
368
878
851
203
263
248
473
284
158
1913
158
68
221
248
4253
608
158
137
788
608
158
743
74
203
1418
113
473
22964
473
83
1418
68
221
4388
263
68
2363
116
158
203
158
1283
1985
68
158
413
1418
851
1418
878...

result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#696154#9248. An Easy Math ProblemCore_65536TL 283ms5484kbC++231.2kb2024-10-31 21:41:422024-10-31 22:20:01

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

unordered_map<int, int> mpp;
void solve()
{
   
        ll n;
        cin>>n;
        if(mpp.count(n)){
            cout<<mpp[n]<<endl;
            return ;
        }
        // n=10000000000;
        vector<ll > pq;
        for(ll i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                pq.push_back(i);
                if(i!=n/i) pq.push_back(n/i);
            }
        }
        sort(pq.begin(),pq.end());
        set<pair<ll,ll> >ans;
        
        for(int i=0;i<pq.size();i++)
        {
            for(int j=i;j<pq.size();j++)
            {
                if(n%(pq[i]*pq[j])==0)
                {
                    ll g=__gcd(pq[i],pq[j]);
                    ans.insert({pq[i]/g,pq[j]/g});
                }
                if(pq[i]*pq[j]>n) break;
            }
        }
        
        cout<<ans.size();
        mpp[n] = ans.size();
        cout<<endl;
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    
    return 0;
}