QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647448#9248. An Easy Math ProblemMu_Silk#WA 50ms3816kbC++201.2kb2024-10-17 14:16:002024-10-17 14:16:00

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-17 14:16:00]
  • Judged
  • Verdict: WA
  • Time: 50ms
  • Memory: 3816kb
  • [2024-10-17 14:16:00]
  • Submitted

answer

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

const int N=100010;
vector<ll> pri;
bool vis[N];
void init(){
    for(int i=2;i<N;i++){
        if(!vis[i])pri.push_back(i);
        for(int j=0;pri[j]*i<N;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

void solve(){
    ll n;cin>>n;
    ll t=n;
    vector<int> v;
    for(int i=0;pri[i]*pri[i]<=t;i++){
        if(t%pri[i]==0){
            int cnt=0;
            while(t%pri[i]==0){
                t/=pri[i];
                cnt++;
            }
            v.push_back(cnt);
        }
    }
    if(t>1)v.push_back(1);
    ll ans=0;
    
    int sz=v.size();
    for(int i=0;i<(1<<sz);i++){
        ll t1=1,t2=1;
        for(int j=0;j<sz;j++){
            if(i>>j&1)t1=t1*(v[j]+1);
            else t2=t2*(v[j]+1);
        }
        ans+=(t1-1)*(t2-1);
    }
    ans/=2;
    // cout<<ans<<" ";

    t=1;
    for(auto i:v)t=t*(i+1);
    ans+=t;
    cout<<ans<<"\n";
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Wrong Answer
time: 50ms
memory: 3816kb

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:

466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775
466775...

result:

wrong answer 1st lines differ - expected: '29525', found: '466775'