QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666533#9248. An Easy Math Problemred#RE 2ms5428kbC++201.4kb2024-10-22 18:56:392024-10-22 18:56:49

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-22 18:56:49]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 5428kb
  • [2024-10-22 18:56:39]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=1e5+10;
int prime[N],vis[N],tmp[N];
int num=0;
void init(int n=1e5)
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i]) prime[++num]=i,tmp[i]=i;
        for(int j=1;j<=num&&prime[j]*i<=n;++j)
        {
            vis[i*prime[j]]=1;
            tmp[i*prime[j]]=i;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
}
void solve()
{
    int n;cin>>n;
    // typedef array<int,2> pr;
    // map<pr,int> cnt;
    vector<int> p(n+1);
    for(int i=1;i<=num;++i)
    {
        int y=prime[i];
        if(n%y==0)
        {
            int cnt=0;
            while(n%y==0)
            {
                n/=y;
                ++cnt;
            }
            p.emplace_back(cnt);
        }
    }
    if(n!=1) p.emplace_back(1);

    vector<int> f(1000);
    f[0]=1;
    int tot=0;
    for(int x:p)
    {
        for(int i=tot;i>=1;--i)
        {
            f[i]+=f[i-1]*x*2;
        }
        ++tot;
    }
    int ans=0;
    for(int i=1;i<=tot;++i) ans+=f[i];
    ans/=2;
    cout<<ans+1<<'\n';
}


signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cin.tie(0);
    int t=1;
    init();
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5428kb

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

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: