QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#840397#9799. Magical Palettefrankly6#TL 156ms12504kbC++172.2kb2025-01-02 18:12:062025-01-02 18:12:13

Judging History

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

  • [2025-01-02 18:12:13]
  • 评测
  • 测评结果:TL
  • 用时:156ms
  • 内存:12504kb
  • [2025-01-02 18:12:06]
  • 提交

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: 5804kb

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: 117ms
memory: 10172kb

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: 113ms
memory: 11536kb

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: 3748kb

input:

1
2 500000

output:

No

result:

ok 1 cases (1 test case)

Test #5:

score: 0
Accepted
time: 64ms
memory: 11848kb

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: 3624kb

input:

1
500000 2

output:

No

result:

ok 1 cases (1 test case)

Test #7:

score: 0
Accepted
time: 60ms
memory: 12504kb

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: 3692kb

input:

1
3 333333

output:

No

result:

ok 1 cases (1 test case)

Test #9:

score: 0
Accepted
time: 44ms
memory: 10112kb

input:

1
3 333332

output:

Yes
1 3 5 
1 172132 344263 516394 688525 860656 32791 204922 377053 549184 721315 893446 65581 237712 409843 581974 754105 926236 98371 270502 442633 614764 786895 959026 131161 303292 475423 647554 819685 991816 163951 336082 508213 680344 852475 24610 196741 368872 541003 713134 885265 57400 22953...

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: 9012kb

input:

1
333332 3

output:

Yes
1 172132 344263 516394 688525 860656 32791 204922 377053 549184 721315 893446 65581 237712 409843 581974 754105 926236 98371 270502 442633 614764 786895 959026 131161 303292 475423 647554 819685 991816 163951 336082 508213 680344 852475 24610 196741 368872 541003 713134 885265 57400 229531 40166...

result:

ok 1 cases (1 test case)

Test #12:

score: 0
Accepted
time: 40ms
memory: 9952kb

input:

1
4 249999

output:

Yes
1 4 7 10 
1 129101 258201 387301 516401 645501 774601 903701 32805 161905 291005 420105 549205 678305 807405 936505 65609 194709 323809 452909 582009 711109 840209 969309 98413 227513 356613 485713 614813 743913 873013 2117 131217 260317 389417 518517 647617 776717 905817 34921 164021 293121 422...

result:

ok 1 cases (1 test case)

Test #13:

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

input:

1
249998 4

output:

No

result:

ok 1 cases (1 test case)

Test #14:

score: 0
Accepted
time: 156ms
memory: 8280kb

input:

1
14925 67

output:

Yes
1 1073 2145 3217 4289 5361 6433 7505 8577 9649 10721 11793 12865 13937 15009 16081 17153 18225 19297 20369 21441 22513 23585 24657 25729 26801 27873 28945 30017 31089 32161 33233 34305 35377 36449 37521 38593 39665 40737 41809 42881 43953 45025 46097 47169 48241 49313 50385 51457 52529 53601 546...

result:

ok 1 cases (1 test case)

Test #15:

score: -100
Time Limit Exceeded

input:

1
1526 655

output:


result: