QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #1095 | #696177 | #9248. An Easy Math Problem | Core_65536 | Core_65536 | Success! | 2024-10-31 22:00:29 | 2024-10-31 22:00:30 |
Details
Extra Test:
Time Limit Exceeded
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:
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #696177 | #9248. An Easy Math Problem | Core_65536 | TL | 944ms | 5360kb | C++23 | 955b | 2024-10-31 21:44:14 | 2024-10-31 22:10:12 |
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)
{
// n:i n/i
pq.push_back(i);
if(i!=n/i) pq.push_back(n/i);
}
}
set<pair<ll ,ll > > ans;
for(auto t:pq)
{
for(ll i=1;i*i<=t;i++)
{
if(t%i==0)
{
ll st=__gcd(i,t/i);
ans.insert({i/st,(t/i)/st});
}
}
}
cout<<ans.size()<<endl;
mpp[n] = ans.size();
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}