QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#840403 | #9799. Magical Palette | frankly6# | TL | 268ms | 11504kb | C++17 | 2.2kb | 2025-01-02 18:14:26 | 2025-01-02 18:14:30 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<ctime>
#include<random>
using namespace std;
const int MX=1000010;
int T, N, M;
int ar[MX], br[MX];
bool vis[MX];
vector<int> va, vb;
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}
int main()
{
// freopen("testdata.in","r",stdin);
// freopen("testdata.out","w",stdout);
T=read();
while(T--)
{
va.clear(); vb.clear();
N=read(); M=read();
int p=N*M;
bool ck=0;
if(gcd(N,M)!=1) {cout << "No\n"; continue;}
for(int i=N;i>=1;i--)
if(gcd(i,N)==1) va.push_back(i);
shuffle(va.begin()+1,va.end(),default_random_engine(time(0)));
for(int i=M;i>=1;i--)
if(gcd(i,M)==1) vb.push_back(i);
shuffle(vb.begin()+1,vb.end(),default_random_engine(time(0)));
for(auto a:va)
{
for(auto b:vb)
{
if(gcd(a,b)!=1) continue;
// cout << "a=" << a << ", b=" << b << '\n';
for(int i=1;i<=N;i++) ar[i]=(1+1ll*(i-1)*a)%p;
for(int i=1;i<=M;i++) br[i]=(1+1ll*(i-1)*b)%p;
bool tag=0;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
int now=(1ll*ar[i]*br[j])%p;
if(vis[now]) {tag=1; break;}
vis[now]=1;
}
if(tag) break;
}
if(!tag) {ck=1; break;}
for(int i=0;i<=N*M;i++) vis[i]=0;
}
if(ck) break;
}
if(ck)
{
cout << "Yes\n";
for(int i=1;i<=N;i++) cout << ar[i] << " "; cout << '\n';
for(int i=1;i<=M;i++) cout << br[i] << " "; cout << '\n';
}
// else cout << "No\n";
for(int i=0;i<=N*M;i++) vis[i]=0;
}
return (0-0);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7792kb
input:
2 2 3 2 2
output:
Yes 1 2 1 3 5 No
result:
ok 2 cases (2 test cases)
Test #2:
score: 0
Accepted
time: 111ms
memory: 10336kb
input:
1 1 1000000
output:
Yes 1 1 0 999999 999998 999997 999996 999995 999994 999993 999992 999991 999990 999989 999988 999987 999986 999985 999984 999983 999982 999981 999980 999979 999978 999977 999976 999975 999974 999973 999972 999971 999970 999969 999968 999967 999966 999965 999964 999963 999962 999961 999960 999959 99...
result:
ok 1 cases (1 test case)
Test #3:
score: 0
Accepted
time: 110ms
memory: 11504kb
input:
1 1000000 1
output:
Yes 1 0 999999 999998 999997 999996 999995 999994 999993 999992 999991 999990 999989 999988 999987 999986 999985 999984 999983 999982 999981 999980 999979 999978 999977 999976 999975 999974 999973 999972 999971 999970 999969 999968 999967 999966 999965 999964 999963 999962 999961 999960 999959 99995...
result:
ok 1 cases (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 2 500000
output:
No
result:
ok 1 cases (1 test case)
Test #5:
score: 0
Accepted
time: 57ms
memory: 11100kb
input:
1 2 499999
output:
Yes 1 2 1 499999 999997 499997 999995 499995 999993 499993 999991 499991 999989 499989 999987 499987 999985 499985 999983 499983 999981 499981 999979 499979 999977 499977 999975 499975 999973 499973 999971 499971 999969 499969 999967 499967 999965 499965 999963 499963 999961 499961 999959 499959 99...
result:
ok 1 cases (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 500000 2
output:
No
result:
ok 1 cases (1 test case)
Test #7:
score: 0
Accepted
time: 59ms
memory: 10396kb
input:
1 499999 2
output:
Yes 1 499999 999997 499997 999995 499995 999993 499993 999991 499991 999989 499989 999987 499987 999985 499985 999983 499983 999981 499981 999979 499979 999977 499977 999975 499975 999973 499973 999971 499971 999969 499969 999967 499967 999965 499965 999963 499963 999961 499961 999959 499959 999957 ...
result:
ok 1 cases (1 test case)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
1 3 333333
output:
No
result:
ok 1 cases (1 test case)
Test #9:
score: 0
Accepted
time: 42ms
memory: 8932kb
input:
1 3 333332
output:
Yes 1 3 5 1 321880 643759 965638 287521 609400 931279 253162 575041 896920 218803 540682 862561 184444 506323 828202 150085 471964 793843 115726 437605 759484 81367 403246 725125 47008 368887 690766 12649 334528 656407 978286 300169 622048 943927 265810 587689 909568 231451 553330 875209 197092 518...
result:
ok 1 cases (1 test case)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 333333 3
output:
No
result:
ok 1 cases (1 test case)
Test #11:
score: 0
Accepted
time: 52ms
memory: 8224kb
input:
1 333332 3
output:
Yes 1 6862 13723 20584 27445 34306 41167 48028 54889 61750 68611 75472 82333 89194 96055 102916 109777 116638 123499 130360 137221 144082 150943 157804 164665 171526 178387 185248 192109 198970 205831 212692 219553 226414 233275 240136 246997 253858 260719 267580 274441 281302 288163 295024 301885 3...
result:
ok 1 cases (1 test case)
Test #12:
score: 0
Accepted
time: 35ms
memory: 8928kb
input:
1 4 249999
output:
Yes 1 4 7 10 1 224469 448937 673405 897873 122345 346813 571281 795749 20221 244689 469157 693625 918093 142565 367033 591501 815969 40441 264909 489377 713845 938313 162785 387253 611721 836189 60661 285129 509597 734065 958533 183005 407473 631941 856409 80881 305349 529817 754285 978753 203225 4...
result:
ok 1 cases (1 test case)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 249998 4
output:
No
result:
ok 1 cases (1 test case)
Test #14:
score: 0
Accepted
time: 268ms
memory: 8344kb
input:
1 14925 67
output:
Yes 1 10319 20637 30955 41273 51591 61909 72227 82545 92863 103181 113499 123817 134135 144453 154771 165089 175407 185725 196043 206361 216679 226997 237315 247633 257951 268269 278587 288905 299223 309541 319859 330177 340495 350813 361131 371449 381767 392085 402403 412721 423039 433357 443675 45...
result:
ok 1 cases (1 test case)
Test #15:
score: -100
Time Limit Exceeded
input:
1 1526 655