QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#800429	#9619. 乘积，欧拉函数，求和	DarwinA66	WA	1629ms	6548kb	C++20	2.9kb	2024-12-06 10:35:29	2024-12-06 10:35:31

Judging History

你现在查看的是最新测评结果

[2024-12-06 10:35:31]
评测

测评结果：WA
用时：1629ms
内存：6548kb

查看

[2024-12-06 10:35:29]
提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3010;
ll mod=998244353;
ll n;
ll pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll a[N],s[N],v[N];
ll id[N];
ll st[1<<16];
ll dp[1<<16];
ll add_dp[1<<16];
ll tp[1<<16];
ll add_tp[1<<16];
bool cmp(ll x,ll y)
{
    return v[x]<v[y];
}
ll fastpow(ll x,ll p)
{
    ll base=x;
    ll res=1ll;
    while(p)
    {
        if(p&1ll)res=(res*base)%mod;
        base=(base*base)%mod;
        p>>=1ll;
    }
    return res;
}
ll mod_inverse(ll x)
{
    ll res=fastpow(x,mod-2);
    return res;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        id[i]=i*1ll;
        ll temp=a[i];
        ll max_p=1ll;
        for(int j=0;j<16;j++)
        {
            while(temp%pri[j]==0)
            {
                temp/=pri[j];
                s[i]|=1ll<<j;
                max_p=pri[j]*1ll;
            }
        }
        if(temp>1)v[i]=temp;
        else v[i]=max_p;
    }
    sort(id+1,id+1+n);
    for(ll mask=0;mask<1ll<<16;mask++)
    {
        ll temp=1ll;
        for(int j=0;j<16;j++)
        {
            if(mask&(1ll<<j))
            {
                temp=(temp*(pri[j]-1ll))%mod;
                temp=(temp*mod_inverse(pri[j]))%mod;
            }
        }
        st[mask]=temp;
    }
    dp[0]=1ll;
    for(int i=1;i<=n;i++)
    {
        for(ll mask=0;mask<(1ll<<16);mask++)
        {
            add_dp[mask]=0ll;
            add_tp[mask]=0ll;
        }
        if(v[id[i]]<=53)
        {
            for(ll mask=0;mask<(1<<16);mask++)
            {
                add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+((dp[mask]*a[id[i]])%mod))%mod;
            }
            for(ll mask=0;mask<(1<<16);mask++)
            {
                dp[mask]=(dp[mask]+add_dp[mask])%mod;
            }
        }
        else
        {
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+(dp[mask]*((v[id[i]]-1)*(a[i]/v[id[i]])))%mod)%mod;
                add_tp[mask|s[id[i]]]=(add_tp[mask|s[id[i]]]+((tp[mask]*a[id[i]])%mod))%mod;
            }
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                tp[mask]=(((tp[mask]+add_dp[mask])%mod)+add_tp[mask])%mod;
            }
            if((v[id[i+1]!=v[id[i]]])||i==n)
            {
                for(ll mask=0;mask<(1<<16);mask++)
                {
                    dp[mask]=(dp[mask]+tp[mask])%mod;
                    tp[mask]=0;
                }
            }
        }
    }
    ll ans=0ll;
    for(ll mask=0;mask<(1<<16);mask++)
    {
        ans=(ans+(dp[mask]*st[mask])%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
/*
20
1 1 11 121 255 289 1888 885 788 1145 2242 2714 2211 2948 2803 2927 764 661 1858 1949
372472595
*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 130ms

memory: 5992kb

input:

5
1 6 8 6 2

output:

result:

ok single line: '892'

Test #2:

score: 0

Accepted

time: 126ms

memory: 5912kb

input:

5
3 8 3 7 8

output:

result:

ok single line: '3157'

Test #3:

score: 0

Accepted

time: 1617ms

memory: 6544kb

input:

2000
79 1 1 1 1 1 1 2803 1 1 1 1 1 1 1609 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2137 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 613 1 499 1 211 1 2927 1 1 1327 1 1 1123 1 907 1 2543 1 1 1 311 2683 1 1 1 1 2963 1 1 1 641 761 1 1 1 1 1 1 1 1 1 1 1 1489 2857 1 1 1 1 1 1 1 1 1 1 1 1 1 967 1 821 1 1 1 1 2143 1861...

output:

50965652

result:

ok single line: '50965652'

Test #4:

score: 0

Accepted

time: 1629ms

memory: 6548kb

input:

2000
1 1 1 1 1 1 1 1 353 1 1 1 557 1 1 1 1 1 1 1 1 1 1 1 1423 1 1 1327 1 1 1 907 1 1 1 1 1 2971 1 1 1 2531 1 1 1 1 1 1 1 1 1 2099 1 1 1 1 1 1 1 1 1 1 1 1 1 1 199 2999 1 727 1 1 1 1 1 1 1 71 1 1 1 1 1 1 2503 1 176 1 1 1 1 1 1 1361 1013 1 1 1 1 1 1 1 2699 1 1 1 1 1 1 1 1 1 2897 1 1 1 1 1637 1 1 1367 1...

output:

420709530

result:

ok single line: '420709530'

Test #5:

score: 0

Accepted

time: 148ms

memory: 5852kb

input:

30
37 14 35 33 38 42 46 3 26 7 16 1 35 38 48 3 43 49 18 3 29 1 43 43 20 6 39 20 14 38

output:

262613273

result:

ok single line: '262613273'

Test #6:

score: 0

Accepted

time: 144ms

memory: 6420kb

input:

30
39 31 49 2 4 28 30 12 13 34 7 28 17 37 38 18 41 33 29 36 18 7 3 14 30 42 35 14 18 35

output:

234142118

result:

ok single line: '234142118'

Test #7:

score: -100

Wrong Answer

time: 287ms

memory: 6500kb

input:

200
53 37 234 248 66 30 64 181 38 130 250 27 199 226 43 185 207 241 38 296 68 18 145 20 64 127 57 30 168 267 221 116 115 192 17 26 5 63 3 127 52 48 229 58 69 111 20 244 234 35 48 217 179 189 89 60 285 106 43 104 36 28 62 281 104 38 281 264 140 275 105 20 203 271 222 262 123 10 82 263 118 254 229 222...

output:

119629509

result:

wrong answer 1st lines differ - expected: '617035263', found: '119629509'