QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303471 | #7688. Alea Iacta Est | zhouhuanyi | WA | 13ms | 12124kb | C++14 | 2.4kb | 2024-01-12 16:26:09 | 2024-01-12 16:26:09 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 1000000
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],tong[N+1],tong2[N+1],length,length2;
bool nprime[N+1];
long long res,ans;
int main()
{
int rt,x,y,d;
v[1]=1;
for (int i=2;i<=N;++i)
if (!nprime[i])
{
v[i]=i;
for (int j=(i<<1);j<=N;j+=i)
{
nprime[j]=1;
if (!v[j]) v[j]=i;
}
}
T=read();
while (T--)
{
n=read(),m=read(),res=1ll*n*m,ans=inf,rt=length=length2=0;
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,length=length2=0;
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;
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("");
}
else
{
d=v[gcd(n,m)],length=length2=0;
if (d!=1&&(d!=n||d!=m))
{
for (int i=0;i<n/d;++i)
for (int j=0;j<d;++j)
tong[++length]=i*d+j*(m/d)+1;
for (int i=0;i<m/d;++i)
for (int j=0;j<d;++j)
tong2[++length2]=i+j+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("");
}
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;
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("");
}
else
{
printf("%d\n",n+(m<<1));
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 11716kb
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: -100
Wrong Answer
time: 13ms
memory: 12124kb
input:
1 40013 40013
output:
120039 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...
result:
wrong answer Integer parameter [name=ai] equals to 80026, violates the range [1, 80025] (test case 1)