QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#840389#9799. Magical Palettefrankly6#TL 110ms11388kbC++171.9kb2025-01-02 18:01:462025-01-02 18:01:46

Judging History

This is the latest submission verdict.

  • [2025-01-02 18:01:46]
  • Judged
  • Verdict: TL
  • Time: 110ms
  • Memory: 11388kb
  • [2025-01-02 18:01:46]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<vector>
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);
    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=1;i<=N;i++)
            if(gcd(i,N)==1) va.push_back(i);
        for(int i=1;i<=M;i++)
            if(gcd(i,M)==1) vb.push_back(i);
        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: 5584kb

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: 110ms
memory: 10880kb

input:

1
1 1000000

output:

Yes
1 
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 1 cases (1 test case)

Test #3:

score: 0
Accepted
time: 94ms
memory: 11388kb

input:

1
1000000 1

output:

Yes
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 1 cases (1 test case)

Test #4:

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

input:

1
2 500000

output:

No

result:

ok 1 cases (1 test case)

Test #5:

score: 0
Accepted
time: 58ms
memory: 10060kb

input:

1
2 499999

output:

Yes
1 2 
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 17...

result:

ok 1 cases (1 test case)

Test #6:

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

input:

1
500000 2

output:

No

result:

ok 1 cases (1 test case)

Test #7:

score: 0
Accepted
time: 61ms
memory: 9936kb

input:

1
499999 2

output:

Yes
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175...

result:

ok 1 cases (1 test case)

Test #8:

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

input:

1
3 333333

output:

No

result:

ok 1 cases (1 test case)

Test #9:

score: -100
Time Limit Exceeded

input:

1
3 333332

output:


result: