QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101841#6351. Exact Subsequenceszhouhuanyi#AC ✓7ms3748kbC++111.4kb2023-05-01 13:51:502023-05-01 13:51:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-01 13:51:52]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3748kb
  • [2023-05-01 13:51:50]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#define N 1000
#define inf 2e9
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 gcd(int x,int y)
{
    if (!y) return x;
    return gcd(y,x%y);
}
int T,n,k,leng,st[N+1],length,tong[N+1];
long long res;
void solve(int x,int y)
{
    if (x==1&&y==1) return;
    if (x<y) tong[++length]=(y-1)/x,solve(x,y-(y-1)/x*x);
    else tong[++length]=(x-1)/y,solve(x-(x-1)/y*y,y);
    return;
}
void dfs(int x,int d,int dres,int tres)
{
    if (x==leng+1)
    {
	res+=d/dres*tres;
	return;
    }
    dfs(x+1,d,dres,tres),dfs(x+1,d,dres*st[x],-tres);
    return;
}
int calc(int x)
{
    res=0,dfs(1,x,1,1);
    return res;
}
int main()
{
    int x,rt;
    T=read();
    while (T--)
    {
	n=read(),x=n+2,k=read(),length=leng=0;
	for (int i=2;i*i<=n+2;++i)
	    if (x%i==0)
	    {
		st[++leng]=i;
		while (x%i==0) x/=i;
	    }
	if (x!=1) st[++leng]=x;
	if (k>calc(n+1))
	{
	    puts("-1");
	    continue;
	}
	rt=0;
	for (int i=log(inf)/log(2);i>=0;--i)
	    if (rt+(1<<i)<=n+1&&calc(rt+(1<<i))<k)
		rt+=(1<<i);
	rt++,solve(rt,n+2-rt);
	printf("%d %d\n",length,rt>n+2-rt);
	for (int i=1;i<=length;++i) printf("%d ",tong[i]);
	puts("");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8
3 1
3 2
3 3
3 4
3 5
1000000000 1
99824 4353
2129721 207087

output:

1 0
3 
2 0
1 1 
2 1
1 1 
1 1
3 
-1
1 0
1000000000 
11 0
9 2 2 1 6 2 1 2 7 1 1 
9 0
9 9 8 2 4 4 3 5 3 

result:

ok 42 numbers

Test #2:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

100
716270982 22102638
553198855 114744220
973042933 952648509
411855162 12679271
376478639 766516692
701616593 797071538
567088052 832850102
231532599 350649206
638081144 950645496
769653386 879396229
641178981 7765699
683883038 664333826
193902679 953508821
399344120 470742245
477410846 571075073
...

output:

17 0
12 3 1 3 1 1 18 1 8 1 2 3 5 1 3 11 2 
19 0
2 5 1 1 9 9 2 2 1 6 1 4 3 2 1 1 2 4 2 
-1
21 0
12 3 1 5 1 1 3 5 1 1 3 1 1 1 19 2 1 1 1 1 3 
-1
-1
-1
-1
-1
-1
18 0
78 1 9 4 1 1 1 1 3 1 1 5 1 1 1 16 2 5 
-1
-1
-1
-1
-1
16 0
1 6 1 3 1 1 21 2 30 2 15 2 5 1 1 4 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
16 0
2 5 ...

result:

ok 516 numbers

Test #3:

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

input:

100
803577926 732588284
959524552 483692625
937450949 420573788
394257859 670341039
468416448 316269090
710340143 302537836
914428480 585041837
849300324 990185122
893426960 565815587
601153216 726270361
820206654 408906693
809261091 899294748
482302622 501315087
415385715 149723632
473655879 445673...

output:

-1
-1
19 0
1 7 1 1 2 1 43 1 32 2 1 1 1 1 7 1 15 1 1 
-1
-1
17 1
1 5 2 2 1 1 46 1 1 2 2 2 10 2 2 7 8 
-1
-1
-1
-1
18 1
341 1 2 1 1 1 1 4 1 1 6 4 1 1 1 9 1 11 
-1
-1
21 0
1 1 2 3 1 15 1 1 2 11 1 5 1 9 2 1 1 2 1 2 2 
17 1
15 1 12 1 2 1 1 5 1 1 1 1 16 5 15 1 5 
-1
17 1
1 3 9 1 5 1 59 1 6 2 2 1 1 25 1 1 ...

result:

ok 596 numbers

Test #4:

score: 0
Accepted
time: 7ms
memory: 3584kb

input:

100
310973933 1
851906850 1
506991370 1
812835085 1
184055713 1
330046155 1
742234340 1
35064224 1
428641100 1
742376022 1
854982930 1
934966715 1
11821239 1
24666398 1
953701756 1
283022550 1
652857323 1
225091259 1
443560524 1
646130347 1
704023856 1
225047814 1
643039211 1
10434355 1
142462737 1
...

output:

1 0
310973933 
1 0
851906850 
1 0
506991370 
1 0
812835085 
1 0
184055713 
1 0
330046155 
1 0
742234340 
1 0
35064224 
1 0
428641100 
1 0
742376022 
1 0
854982930 
1 0
934966715 
1 0
11821239 
1 0
24666398 
1 0
953701756 
1 0
283022550 
1 0
652857323 
1 0
225091259 
1 0
443560524 
1 0
646130347 
1 0...

result:

ok 300 numbers

Test #5:

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

input:

100
189 575154303
244 513866599
724 893121161
460 783742901
791 932434605
602 341436697
920 357555133
938 708487917
652 277902399
588 246605698
268 208941807
19 820801694
79 546956091
383 505858553
727 722075077
19 573727679
863 991923941
551 733860625
436 76355365
102 899550340
73 950034371
433 732...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 6ms
memory: 3576kb

input:

100
223092868 522742773
223092868 278957336
223092868 10795972
223092868 933104349
223092868 703746065
223092868 499801401
223092868 87818865
223092868 690822764
223092868 773395398
223092868 714043760
223092868 510458728
223092868 528769614
223092868 59550625
223092868 975799724
223092868 830655839...

output:

-1
-1
15 0
2 2 1 1 1 2 4 4 2 15 3 8 15 1 10 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
18 0
5 1 1 8 1 1 2 1 46 1 5 5 1 5 3 1 1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
19 0
3 1 5 1 3 1 ...

result:

ok 204 numbers

Test #7:

score: 0
Accepted
time: 4ms
memory: 3732kb

input:

100
999999935 310403983
999999935 72364213
999999935 397038456
999999935 75080336
999999935 454985457
999999935 778137418
999999935 478883812
999999935 588122347
999999935 651540264
999999935 650019250
999999935 584491303
999999935 852022109
999999935 204794560
999999935 38478503
999999935 633363053...

output:

16 0
2 4 1 1 19 1 1 5 2 2 2 21 1 3 1 107 
13 0
12 1 4 1 1 9 1 3 82 1 78 1 22 
19 0
1 1 1 12 1 9 1 2 2 1 1 2 7 3 23 11 1 1 1 
12 0
12 3 7 2 4 1 45 2 2 2 4 118 
16 0
1 5 18 1 1 2 144 3 1 1 5 5 2 1 4 1 
23 1
3 1 1 33 1 3 3 3 2 1 1 1 4 1 1 1 1 8 1 1 1 2 3 
20 0
1 11 2 1 18 29 1 3 2 3 1 1 2 1 1 1 1 1 1 7...

result:

ok 1869 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3368kb

input:

100
2 948507270
2 461613425
2 139535653
2 575270914
2 738803143
2 726699316
2 103994146
2 249524708
2 922817781
2 838029880
2 667513691
2 439784727
2 821461860
2 581510875
2 990481633
2 337473349
2 648674686
2 323922097
2 905107222
2 325476490
2 221111618
2 768519935
2 38017075
2 968148470
2 2181080...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 6ms
memory: 3748kb

input:

100
994593598 798824698
994593598 836802674
994593598 681520523
994593598 794670609
994593598 473875349
994593598 10246152
994593598 185505534
994593598 890463296
994593598 99179674
994593598 495304199
994593598 834562731
994593598 674734647
994593598 725257131
994593598 1210263
994593598 172395848
...

output:

-1
-1
-1
-1
-1
19 0
16 1 4 4 9 1 4 1 6 3 1 2 1 4 7 1 2 1 1 
-1
-1
15 1
1 5 4 11 3 1 4 1 3 2 1 1 241 5 2 
-1
-1
-1
-1
14 0
149 1 3 2 3 2 1 12 1 2 2 15 1 40 
14 1
17 9 1 7 1 5 30 1 2 1 1 8 11 4 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
18 1
1 8 5 1 2 16 1 2 19 1 1 2 2 2 1 1 11 3 
15 0
8 1 5 9 16 3 3 3 3 9 ...

result:

ok 478 numbers

Test #10:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

100
611471244 7
285534859 285324624
365254431 8
302700479 10
531626021 1
241407326 119249315
960694338 1
444253010 166613760
378833523 7
792109060 10
41233968 1
19856541 1
948544448 1
480404093 428613111
460814812 1
452369404 213580071
792771208 1
108109408 49140485
640233262 1
693587230 237801302
8...

output:

4 0
47036248 1 2 3 
-1
2 0
45656803 7 
2 0
30270047 9 
1 0
531626021 
13 1
81 1 240 1 2 1 1 1 2 31 1 1 5 
1 0
960694338 
16 1
7 3 6 1 11 1 9 2 1 6 2 6 3 6 1 1 
3 0
42092612 1 7 
6 0
27314104 1 1 2 2 1 
1 0
41233968 
1 0
19856541 
1 0
948544448 
-1
1 0
460814812 
-1
1 0
792771208 
-1
1 0
640233262 
-...

result:

ok 689 numbers

Test #11:

score: 0
Accepted
time: 6ms
memory: 3544kb

input:

100
486624528 41
826504481 751367707
277260365 1
198842419 197411751
221851582 80
935299711 1
91749879 1
473820636 154959954
978802934 4
388928056 175983814
453541903 450882755
708135976 1
997863449 1
516874672 1
816187863 533373945
23910223 1
132118186 61473249
585259343 2
816641908 408260772
65256...

output:

3 0
4021689 3 39 
-1
1 0
277260365 
-1
7 0
928248 3 3 1 1 1 5 
1 0
935299711 
1 0
91749879 
16 1
1 1 8 6 36 1 2 2 2 1 7 1 18 2 4 1 
3 0
139828989 1 5 
-1
-1
1 0
708135976 
1 0
997863449 
1 0
516874672 
16 1
4 2 5 1 5 39 2 1 1 11 1 1 2 15 1 8 
1 0
23910223 
-1
2 0
292629671 1 
-1
16 1
2 3 1 11 3 3 20...

result:

ok 596 numbers

Test #12:

score: 0
Accepted
time: 7ms
memory: 3748kb

input:

100
483413348 443
820011935 687
805999661 803837970
880414348 80
370099111 358160589
250102150 98773273
726543000 75
613461382 1
86774162 1
891363559 867271687
30278513 704
112738310 215
89445142 44709732
75764504 776
702277221 443543882
678216524 1
274629757 1
304066337 930
104562487 1
654995466 21...

output:

7 0
372715 1 1 6 19 1 3 
6 0
1126389 42 1 4 1 1 
-1
6 0
2944528 1 1 2 29 1 
-1
-1
7 0
4876126 1 1 7 1 3 1 
1 0
613461382 
1 0
86774162 
-1
9 0
34445 1 1 4 1 3 1 7 1 
7 0
253343 1 1 11 4 1 2 
-1
8 0
48722 6 2 4 1 2 1 4 
21 1
1 1 2 1 4 1 1 3 2 1 5 2 4 1 8 4 2 1 5 1 8 
1 0
678216524 
1 0
274629757 
6 0...

result:

ok 783 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

100
283550352 94526185
867566523 2944
562028786 254142878
887589426 295811826
145509559 6216
176986027 2331
225110614 2501
44722121 42087327
969367610 1
513981059 8315
682666637 607754222
229626250 74846852
423497030 617
747716605 596923368
656821366 317814670
922276433 350
568171727 551682118
66597...

output:

12 1
2 1675 2 1 7 9 2 4 2 2 1 2 
8 0
190213 9 1 2 6 4 1 3 
15 1
9 2 5 2 2 3 4 8 3 1 1 1 2 8 29 
15 1
3 6 2 2 10 5 6 26 1 11 3 2 1 1 2 
11 0
15606 1 1 2 3 1 1 2 1 4 13 
10 0
46029 5 1 1 1 27 1 1 1 1 
4 0
29700 1 8 841 
17 1
21 1 4 1 1 1 1 2 7 19 1 5 3 1 1 1 1 
1 0
969367610 
7 0
56043 5 1 29 7 3 1 
2...

result:

ok 891 numbers