525 美团杯2020 平行四边形

(Updated: )
(3 mins to read)

给定n*n的棋盘,要求放置n个棋子,满足:

  • x和y都是一个1-n的排列
  • 任意四个棋子不构成平行四边形其中n+1是一个质数

考虑n+1的原根g,则$g,g^2,g^3…g^n%(n+1)$各不相同$(1,g)…(n,g^n$%$(n+1))$即为答案无证明o.O

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
#include <bits/stdc++.h>
using namespace std;
int powmod(int a, int b, int m)
{
  int ans = 1;
  while(b)
  {
    if(b&1) ans = 1ll*ans*a%m;
    a = 1ll*a*a%m;
    b >>= 1;
  }
  return ans;
}
int phi(int x)
{
  int ans = x;
  for(int i=2; i*i<=x; i++)
  {
    if(x%i==0)
    {
      ans -= ans / i;
      while(x%i==0) x /= i;
    }
  }
  if(x>1) ans -= ans / x;
  return ans;
}
void solve()
{
  int n;
  scanf("%d", &n);
  int c = phi(n+1), g = 0;
  bool ok = 0;
  while(++g)
  {
    ok = (powmod(g, c, n+1)==1);
    int tmpc = c;
    for(int i=2; i*i<=tmpc&&ok; i++)
    {
      if(tmpc%i==0)
      {
        while(tmpc%i==0) tmpc /= i;
        if(powmod(g, c/i, n+1)==1) ok = 0;
      }
    }
    if(tmpc>1&&powmod(g, c/tmpc, n+1)==1) ok = 0;
    if(ok) break;
  }
  int ans = g;
  for(int i=1; i<=n; i++)
  {
    printf("%d %d\n", i, ans);
    ans = ans*g%(n+1);
  }
}
int main()
{
  int t;
  scanf("%d", &t);
  while(t--) solve();
  return 0;
}