梦熊 NOIP 13连测 #3

A.

赛事找规律找到了，可惜差一步，然后用了oies。

1. 欧拉定理：若 \(gcd(a, m) = 1\)，则 \(a^{\phi(m)} \equiv 1 (mod \ m)\)。

发现 1 和 \(2n\) 永远都不会动，并且当 2 归位时，整套牌也都归位了，所以先只考虑 2 的位置变化。

如果 \(n\) 无线大，第 \(i\) 次操作后 2 的位置为 \(2^i + 1\)。考虑上 \(n\) 的大小，第 \(i\) 次操作后的位置为 \((2^i + 1) \% (2n - 1)\) 。

2. 归为即为求最小的 \(i\) 使得 \((2^i + 1) \% (2n - 1) = 2\)，即为 \((2^i - 1) \% (2n - 1) = 0\), \(2^i \equiv 1 (mod \ 2n - 1)\)。

再由欧拉定理得 \(i\) 一定为 \(\phi(2n - 1)\) 的因子，枚举 \(\phi(2n - 1)\) 的因子即可，时间复杂度 \(O(\sqrt n)\)。

#include<bits/stdc++.h>
#define int __int128
using namespace std;

const int N = 1e6 + 7;
int mod;
int qpow(int a, int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res % mod;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}void solve() {
	int n;
	n = read();
	int m = phi(2 * n - 1);
	int ans = 0;
	mod = 2 * n - 1;
	for(int i = 1; i * i <= m; i ++) {
		if(m % i == 0) {
			if(qpow(2, i) == 1 % mod) {
				write(i);
				cout << endl;
				return;
			}
			if(i * i != m && qpow(2, m / i) == 1 % mod) ans = m / i;
		}
	}
	write(ans);
	cout << endl;
}
signed main() {
	freopen("card.in", "r", stdin);
	freopen("card.out", "w", stdout);
	int T;
	T = read();
	while(T --) solve();
}

B.

原题

设当前异或和为 \(x\)，令 \(a_{n+1} = x\)。不难发现，对 \(a_i\) 操作一次即为交换 \(a_i\) 和 \(a_{n + 1}\)。就可以建边，对于
\(a_i \neq b_i\)，连一条边，答案即为边数 + 连通块数 - 1。

证明

C.

原题

D.