QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85060#5685. 快速 LCM 变换zhouhuanyiAC ✓1802ms188516kbC++233.2kb2023-03-06 22:19:252023-03-06 22:19:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 22:19:26]
  • 评测
  • 测评结果:AC
  • 用时:1802ms
  • 内存:188516kb
  • [2023-03-06 22:19:25]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#define N 2000000
#define M 8000000
#define g 3
#define mod 998244353
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int fast_pow(int a,int b)
{
    int res=1,mul=a;
    while (b)
    {
	if (b&1) res=1ll*res*mul%mod;
	mul=1ll*mul*mul%mod,b>>=1;
    }
    return res;
}
void Adder(int &x,int d)
{
    x+=d;
    if (x>=mod) x-=mod;
    return;
}
void Adder2(int &x,int d)
{
    x+=d;
    if (x<0) x+=mod;
    return;
}
int MD(int x)
{
    return x>=mod?x-mod:x;
}
int MD2(int x)
{
    return x<0?x+mod:x;
}
struct reads
{
    int num,data;
};
int n,rst=1,res,ans,inv[N+1],rev[M+1],r[N+1],maxn[N+1],cmaxn[N+1],cnt[N+1],dp[M+1],delta[M+1];
bool nprime[N+1];
vector<reads>p[N+1];
void NTT(int limit,int *s,int type)
{
    int s1,s2,d;
    for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?(limit>>1):0);
    for (int i=0;i<limit;++i)
	if (rev[i]>i)
	    swap(s[i],s[rev[i]]);
    for (int i=2,w;i<=limit;i<<=1)
    {
	if (type==1) w=fast_pow(g,(mod-1)/i);
	else w=fast_pow(g,(mod-1)/i*(i-1));
	for (int j=0;j+i-1<=limit;j+=i)
	    for (int k=j,wn=1;k<j+(i>>1);++k,wn=1ll*wn*w%mod)
		s1=s[k],s2=1ll*s[k+(i>>1)]*wn%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
    }
    if (type==-1)
    {
	d=fast_pow(limit,mod-2);
	for (int i=0;i<limit;++i) s[i]=1ll*s[i]*d%mod;
    }
    return;
}
int main()
{
    int res,limit=1,x,cst;
    inv[1]=1;
    for (int i=2;i<=N;++i) inv[i]=MD2(-1ll*(mod/i)*inv[mod%i]%mod);
    for (int i=2;i<=N;++i)
	if (!nprime[i])
	{
	    for (int j=(i<<1);j<=N;j+=i) nprime[j]=1;
	}
    for (int i=2;i<=N;++i)
	if (!nprime[i])
	    for (int j=i;j<=N;j+=i)
	    {
		x=j,cst=0;
		while (x%i==0) x/=i,cst++;
		p[j].push_back((reads){i,cst});
	    }
    n=read();
    for (int i=1;i<=n;++i)
    {
	r[i]=read();
	for (int j=0;j<p[r[i]].size();++j) maxn[p[r[i]][j].num]=max(maxn[p[r[i]][j].num],p[r[i]][j].data);
    }
    for (int i=1;i<=N;++i)
	for (int j=1;j<=maxn[i];++j)
	    rst=1ll*rst*i%mod;
    for (int i=1;i<=n;++i)
	for (int j=0;j<p[r[i]].size();++j)
	{
	    if (maxn[p[r[i]][j].num]==p[r[i]][j].data) cnt[p[r[i]][j].num]++;
            else cmaxn[p[r[i]][j].num]=max(cmaxn[p[r[i]][j].num],p[r[i]][j].data);
	}
    for (int i=1;i<=n;++i)
    {
	res=1;
	for (int j=0;j<p[r[i]].size();++j)
	    if (cnt[p[r[i]][j].num]==1&&maxn[p[r[i]][j].num]==p[r[i]][j].data)
		for (int k=1;k<=maxn[p[r[i]][j].num]-cmaxn[p[r[i]][j].num];++k)
		    res=1ll*res*inv[p[r[i]][j].num]%mod;
	Adder(dp[r[i]],res),Adder2(delta[r[i]+r[i]],-1ll*res*res%mod);
    }
    while (limit<=N) limit<<=1;
    NTT(limit,dp,1);
    for (int i=0;i<=limit;++i) dp[i]=1ll*dp[i]*dp[i]%mod;
    NTT(limit,dp,-1);
    for (int i=1;i<=N;++i) Adder(delta[i],dp[i]),delta[i]=1ll*delta[i]*inv[2]%mod;
    for (int i=1;i<=N;++i)
    {
	res=rst;
	for (int j=0;j<p[i].size();++j)
	    for (int k=1;k<=p[i][j].data-maxn[p[i][j].num];++k)
		res=1ll*res*p[i][j].num%mod;
	Adder(ans,1ll*delta[i]*res%mod);
    }
    printf("%d\n",ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1488ms
memory: 187152kb

input:

96709
888451 516254 906133 347209 680059 352562 559092 51645 805639 208345 690286 512761 405948 902987 481307 401690 964462 704714 771809 946054 331027 715301 899161 905069 871833 223641 661393 773039 703447 949204 590357 952617 532852 801806 896897 974849 595373 648200 784789 740171 522959 946981 9...

output:

317859717

result:

ok single line: '317859717'

Test #2:

score: 0
Accepted
time: 1456ms
memory: 185128kb

input:

500000
132179 56907 160114 921536 921536 160114 921536 56907 26017 132179 26017 590365 56907 132179 56907 160114 160114 377247 377247 160114 160114 91200 56907 921536 91200 590365 160114 504174 377247 56907 132179 91200 132179 132179 91200 590365 160114 91200 377247 30631 56907 26017 26017 91200 921...

output:

853619659

result:

ok single line: '853619659'

Test #3:

score: 0
Accepted
time: 1431ms
memory: 183152kb

input:

4883
347062 234948 766629 954124 305767 18582 224896 461186 148474 86197 698808 413499 286357 806937 297603 735016 557034 636363 185180 940722 190964 808094 241391 283851 581235 660421 875791 550632 804950 834718 126518 389136 231188 227150 959147 762772 19367 939679 933098 150368 233339 956109 1808...

output:

385014000

result:

ok single line: '385014000'

Test #4:

score: 0
Accepted
time: 1467ms
memory: 186368kb

input:

27943
217360 702214 253520 779644 556142 556300 386035 757853 984695 864620 619819 13084 664068 973066 174047 873958 726742 653890 781777 411151 703033 301904 58419 159086 700216 896124 871138 302148 125900 351930 462287 173720 269649 186418 304361 286120 958557 411911 18242 744958 409144 677486 143...

output:

214762986

result:

ok single line: '214762986'

Test #5:

score: 0
Accepted
time: 1599ms
memory: 187416kb

input:

186170
310454 97457 958948 823456 848927 176202 899032 488541 373103 770802 335003 362174 693540 851736 752536 830917 501120 553219 337883 839564 394144 538498 580666 90035 932191 272143 449733 663693 993744 474097 595691 58896 170220 477669 936225 836223 855254 620546 992377 545362 46370 163908 836...

output:

75077307

result:

ok single line: '75077307'

Test #6:

score: 0
Accepted
time: 1802ms
memory: 188516kb

input:

461635
597343 754468 767171 132818 668074 941520 687283 259355 434890 187925 960388 573728 677884 252358 526652 656422 709003 194958 96004 556213 506136 530473 242932 105452 365342 742732 946199 158101 771855 733211 510859 644771 549744 56792 393492 274640 291094 870555 31498 866856 865391 117602 11...

output:

937091194

result:

ok single line: '937091194'

Test #7:

score: 0
Accepted
time: 1566ms
memory: 187524kb

input:

194282
700822 989293 924557 450818 445936 129331 932692 788512 320143 46127 609422 750817 616292 816791 62263 744286 16679 206183 66146 98782 775153 436169 654046 957959 886852 217001 471907 619813 565904 492511 674957 868307 466649 648997 309362 229499 787333 23294 633781 288653 297524 964282 76786...

output:

917619265

result:

ok single line: '917619265'

Test #8:

score: 0
Accepted
time: 1683ms
memory: 187812kb

input:

274937
421277 600214 66886 548046 173912 983674 641240 13191 543328 712058 237791 155490 972292 153487 740371 812220 392383 396000 94351 189262 643305 655496 137184 117514 499669 842950 109626 57125 717207 89407 606654 182960 270097 590141 605770 14170 883600 395413 662376 911163 344273 667507 87414...

output:

216164675

result:

ok single line: '216164675'

Test #9:

score: 0
Accepted
time: 1703ms
memory: 188268kb

input:

383978
851871 877586 361600 786208 526058 465064 368789 2497 421862 354594 130900 493744 828354 703585 806951 138487 440549 990454 35846 927839 798279 257958 591659 214523 999499 896942 230281 777473 757874 569698 49428 587726 771296 549685 675264 716837 690729 445449 544004 623061 549322 357348 590...

output:

407714524

result:

ok single line: '407714524'

Test #10:

score: 0
Accepted
time: 1741ms
memory: 188492kb

input:

455853
597761 696372 83500 686162 392679 939871 431141 848570 438287 223903 47070 847771 754034 477428 971806 989734 118635 84249 230083 701866 169021 352675 706546 954030 934478 52915 429165 315039 457715 872533 672806 768061 197745 622182 885533 999945 799179 672700 83573 778177 185958 389570 3607...

output:

721056673

result:

ok single line: '721056673'