QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303685#7688. Alea Iacta EstzhouhuanyiWA 119ms19272kbC++142.0kb2024-01-12 21:08:582024-01-12 21:09:00

Judging History

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

  • [2024-01-12 21:09:00]
  • 评测
  • 测评结果:WA
  • 用时:119ms
  • 内存:19272kb
  • [2024-01-12 21:08:58]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 3000000
using namespace std;
const int inf=(int)(1e9);
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,m,v[N+1],F[N+1],tong[N+1],tong2[N+1],length,length2;
bool nprime[N+1];
long long res,ans;
int main()
{
	int rt,x,y,a,b;
	T=read();
	while (T--)
	{
		n=read(),m=read(),res=1ll*n*m,ans=n+m+min(n,m),rt=a=b=x=y=length=length2=0;
		for (int i=2;i<=n-1;++i)
			if (n%i==0&&gcd(i,n/i)==1)
			{
				for (int j=0;j<n/i;++j)
					if (1ll*i*j<=m&&(m-i*j)%(n/i)==0)
						ans=n+m,a=i,b=n/i;
			}
		for (int i=2;i<=m-1;++i)
			if (m%i==0&&gcd(i,m/i)==1)
			{
				for (int j=0;j<m/i;++j)
					if (1ll*i*j<=n&&(n-i*j)%(m/i)==0)
						ans=n+m,a=i,b=m/i;
			}
		for (int i=1;1ll*i*i<=res;++i)
			if (i!=n&&i!=m&&res%i==0&&i+res/i<ans)
				ans=i+res/i,rt=i;
		if (rt)
		{
			x=gcd(rt,n),y=rt/x;
			for (int i=0;i<x;++i)
				for (int j=0;j<y;++j)
					tong[++length]=i+j+1;
			for (int i=0;i<n/x;++i)
				for (int j=0;j<m/y;++j)
					tong2[++length2]=x*i+y*j+1;
		}
		else if (a)
		{
			for (int i=0;i<a;++i)
				for (int j=0;j<b;++j)
					tong[++length]=i+j+1;
			for (int i=0;i<=n+m;++i) F[i]=0;
			F[0]=1,F[n]=-1,F[m]-=1,F[n+m]=1;
			for (int i=a;i<=n+m;++i) F[i]+=F[i-a];
			for (int i=b;i<=n+m;++i) F[i]+=F[i-b];
			for (int i=0;i<=n+m;++i)
				for (int j=1;j<=F[i];++j)
					tong2[++length2]=i+1;
		}
		else
		{
			if (n<m)
			{
				for (int i=0;i<n;++i) tong[++length]=i+1,tong[++length]=i+1;
				for (int i=0;i<m;++i) tong2[++length2]=i+1;
			}
			else
			{
				for (int i=0;i<n;++i) tong[++length]=i+1;
				for (int i=0;i<m;++i) tong2[++length2]=i+1,tong2[++length2]=i+1;
			}
		}
		printf("%d ",length);
		for (int i=1;i<=length;++i) printf("%d ",tong[i]);
		puts("");
		printf("%d ",length2);
		for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
		puts("");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

3
2 8
1 9
2 9

output:

4 1 2 2 3 
4 1 3 5 7 
3 1 2 3 
3 1 4 7 
3 1 2 3 
6 1 4 7 2 5 8 

result:

ok Correct. (3 test cases)

Test #2:

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

input:

1
40013 40013

output:

40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 3ms
memory: 3804kb

input:

1
40013 1

output:

40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #4:

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

input:

1
2 40013

output:

4 1 1 2 2 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

result:

ok Correct. (1 test case)

Test #5:

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

input:

1
3 40013

output:

6 1 1 2 2 3 3 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ...

result:

ok Correct. (1 test case)

Test #6:

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

input:

1
4 40013

output:

8 1 1 2 2 3 3 4 4 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95...

result:

ok Correct. (1 test case)

Test #7:

score: 0
Accepted
time: 119ms
memory: 15252kb

input:

1
999983 999983

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #8:

score: 0
Accepted
time: 46ms
memory: 7536kb

input:

1
1 999983

output:

2 1 1 
999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

result:

ok Correct. (1 test case)

Test #9:

score: 0
Accepted
time: 42ms
memory: 7548kb

input:

1
2 999983

output:

4 1 1 2 2 
999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

result:

ok Correct. (1 test case)

Test #10:

score: 0
Accepted
time: 35ms
memory: 7552kb

input:

1
999983 3

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #11:

score: 0
Accepted
time: 49ms
memory: 7672kb

input:

1
999983 4

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #12:

score: 0
Accepted
time: 88ms
memory: 19272kb

input:

1
1000000 1000000

output:

1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ...

result:

ok Correct. (1 test case)

Test #13:

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

input:

1
1000000 1

output:

1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #14:

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

input:

1
1000000 2

output:

1250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #15:

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

input:

1
3 1000000

output:

1600 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #16:

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

input:

1
4 1000000

output:

2000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #17:

score: 0
Accepted
time: 101ms
memory: 19096kb

input:

1
988027 988027

output:

988027 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #18:

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

input:

1
988027 1

output:

991 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (1 test case)

Test #19:

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

input:

1
2 988027

output:

997 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (1 test case)

Test #20:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

1
3 988027

output:

997 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (1 test case)

Test #21:

score: 0
Accepted
time: 3ms
memory: 3828kb

input:

1
4 988027

output:

1982 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #22:

score: 0
Accepted
time: 103ms
memory: 19200kb

input:

1
995779 995779

output:

995779 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #23:

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

input:

1
1 995779

output:

983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (1 test case)

Test #24:

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

input:

1
995779 2

output:

1013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #25:

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

input:

1
995779 3

output:

1013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #26:

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

input:

1
995779 4

output:

1966 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...

result:

ok Correct. (1 test case)

Test #27:

score: 0
Accepted
time: 75ms
memory: 14800kb

input:

1
720720 720720

output:

720720 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10 7 8 9 10 11 8 9 10 11 12 9 10 11 12 13 10 11 12 13 14 11 12 13 14 15 12 13 14 15 16 13 14 15 16 17 14 15 16 17 18 15 16 17 18 19 16 17 18 19 20 17 18 19 20 21 18 19 20 21 22 19 20 21 22 23 20 21 22 23 24 21 22 23 24 25 22 23 24 25 2...

result:

ok Correct. (1 test case)

Test #28:

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

input:

1
720720 1

output:

840 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (1 test case)

Test #29:

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

input:

1
2 720720

output:

1170 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #30:

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

input:

1
3 720720

output:

1456 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #31:

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

input:

1
4 720720

output:

1680 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #32:

score: -100
Wrong Answer
time: 63ms
memory: 8928kb

input:

1
524288 524288

output:

262144 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

wrong answer Jury has a better answer. (test case 1)