QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136068#5040. Dirichlet $k$-th rootP3KOWA 192ms6184kbC++20836b2023-08-06 23:27:412023-08-06 23:27:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-06 23:27:42]
  • 评测
  • 测评结果:WA
  • 用时:192ms
  • 内存:6184kb
  • [2023-08-06 23:27:41]
  • 提交

answer

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

typedef long long ll;
const int mod=998244353;
const int MAXN=1e5+5;

ll n,k;

struct ary{
	int a[MAXN];
	ary operator *(const ary y)const{
		ary ans;
		memset(ans.a,0,sizeof ans.a);
		for(int d=1;d<=n;d++)
			for(int j=d;j<=n;j+=d)
				ans.a[j]=(1ll*ans.a[j]+1ll*a[d]*y.a[j/d]%mod)%mod;
		return ans;
	}
}g,ans;

ll qpow(ll x,ll y){
	ll ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

ary qpow(ary x,ll y){
	ary ans;
	ans.a[1]=1;
	while(y){
		if(y&1)ans=ans*x;
		x=x*x;
		y>>=1;
	}
	return ans;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>g.a[i];
	}
	ll inv=qpow(k,mod-2);
	ans=qpow(g,inv);
	if(ans.a[1]!=1)cout<<-1;
	else{
		for(int i=1;i<=n;i++){
			cout<<ans.a[i]<<" ";
		}
	}
}

詳細信息

Test #1:

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

input:

5 2
1 8 4 26 6

output:

1 4 2 5 3 

result:

ok 5 number(s): "1 4 2 5 3"

Test #2:

score: 0
Accepted
time: 5ms
memory: 5792kb

input:

1000 10
1 516238479 765833625 408427111 593035929 984641872 149832309 743527500 533342020 315774476 81082172 461044503 235289865 539969249 564590101 736090497 933661679 394417077 377363949 717587561 143428748 321957671 413061277 166846744 532438287 802900949 101236134 182814904 328306207 83339054 87...

output:

1 750394895 575705539 383612918 758074640 870483127 713754278 172378328 328377975 148157627 607054829 769165678 522651163 979451027 321052733 428161561 792137215 595294435 736507442 784558508 35541967 129771597 141130563 667029666 976562087 614420517 890540347 922620141 132655056 898078185 586990958...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 5744kb

input:

1000 10
1 836321215 611344545 176796302 574251412 137508398 761666720 357050290 801608050 863745155 811911311 829248030 265662561 683320811 920044294 338428495 840771823 558535163 926728514 375903056 522656042 909868778 153190814 812151247 960179729 591861004 169384211 295767075 841728125 81742549 5...

output:

1 582754298 560256631 598696700 656371753 428716095 76166672 762502364 234864311 233488066 380664437 883840099 326039562 115077358 562124625 491468731 982497100 88908472 292321722 938842515 680178128 840510694 214967952 569450139 579949075 97329455 173736151 491492784 583294989 144817858 358079034 9...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 5792kb

input:

1000 10
1 158159598 758845348 641419963 949731479 892599046 605485292 272562963 71629727 807736065 544496098 895461672 992289725 360646418 47025620 104802564 747881967 584699437 779838610 638198320 671654821 729764045 195310235 459211397 159448304 78831175 237532287 408719246 520941761 546171999 897...

output:

1 415113701 475182276 672451493 793744195 950229534 659495141 726381508 631317964 412740072 453747351 272892516 598351149 977147905 739966693 418651375 174612632 596342698 77983861 481155841 428325132 962771540 518653200 864432859 639266798 599162983 114398480 12687680 351567482 742362461 888336134 ...

result:

ok 1000 numbers

Test #5:

score: -100
Wrong Answer
time: 192ms
memory: 6184kb

input:

100000 483386906
1 925386004 817279817 436846237 363754513 36363197 132023702 507929492 314426859 89798592 832041984 299550534 283316534 540665653 105421174 607783420 916340928 533190624 313917727 118229052 732510050 447767998 823833186 132028675 284839462 164439702 201511962 983444172 268467355 346...

output:

1 509298944 768210156 31397754 759101893 80740356 561826331 862564382 840871048 446523741 777685542 905264255 546338384 287746596 545833689 176159038 430279667 722628961 663972399 508456777 441637678 818668691 582753500 541766927 890058957 59127138 430432227 600528851 861723556 273962920 444195967 5...

result:

wrong answer 98714th numbers differ - expected: '453395913', found: '860197235'