1. 数论

1.1 位运算

1. Make Almost Equal With Mod

• 背景 给定一个由 不同正整数 组成的数组，找到一个正整数 k，让数组中的每个元素 $mod$ $k$ 后数组中只包含 $2$ 个不同的值 。题目保证至少存在一个这样的 $k$。如果有多个解，可以打印其中的任意一个。
  
• 思路 方法一：
  方法二：
• 代码

---

hhh

---

1.2 奇偶性

1. Training Before the Olympiad

• 背景

  ​ 给

• 思路

• 代码

---

1.3 常用结论

1. Mathematical Problem（平方数）

• 背景

  ​ 给你一个奇数 $n$，要你找到 $n$ 个长度为 $n$ 的平方数（每个数中的数字都不相同），如果答案有多个，则按任意顺序输出即可。

• 思路 当 $n = 1$ 时，答案为 $1$。

  当 $n = 3$ 时，答案为 $169, 961, 196$。

  当 $n > 3$ 时，对于所有的 $n + 2$ ，将长度为 $n$ 的答案中的每个数字乘以 $100$ 后这些数依然为平方数。此时就还剩 2 个数需要构造。假设他们是这样的：$9...6...1$, $1...6...9$，数字之间的间隙需填上 $(n - 3)/2$ 个 $0$，可以发现他们是 $1...3$，$3...1$（数字之间的间隙需填上 $(n - 3)/2$ 个 $0$）的平方数。

• 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
vector<string> ans[N];

void init()
{
	ans[1].push_back("1");
	ans[3].push_back("169");
	ans[3].push_back("196");
	ans[3].push_back("961");

	for(int i = 5; i <= 99; i += 2){
		for(auto item : ans[i - 2])
			ans[i].push_back(item + "00");
		
		string s1 = "1", s2 = "9";
		int len = (i - 3) / 2;

		for(int j = 0; j < len; ++j)
			s1 += '0', s2 += '0';
		s1 += '6', s2 += '6';

		for(int j = 0; j < len; ++j)
			s1 += '0', s2 += '0';
		s1 += '9', s2 += '1';
		
		ans[i].push_back(s1);
		ans[i].push_back(s2);
	}
}
void solve()
{
	int n;
	cin >> n;

	for(auto item : ans[n])
		cout << item << "\n";
}
int main()
{
	init();
	int t;
	cin >> t;

	while(t--){
		solve();
	}
	return 0;
}

---

2. Two Divisors（因子）

• 背景 给定 $x$（$1 \le x \le 10^9$） 的两个最大因子 $a$ 和 $b$，同时满足 $1 \le a \lt b \lt x$，你需要找到这个 $x$ 的值。可能存在多个答案，只需要输出任意一个即可。
• 思路 如果 $b$ 为 $a$ 的倍数，则 $x$ 为 $b * b / a$。 如果 $b$ 不为 $a$ 的倍数，则 $x$ 为 $a * b / gcd(a, b)$。
  
• 代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

LL gcd(LL a, LL b)
{
	return b ? gcd(b, a % b) : a;
}
void solve()
{
	LL a, b;
	scanf("%lld %lld", &a, &b);

	LL num;
	if(b % a == 0)
		num = b * b / a;
	else
		num = a * b / gcd(a, b);
	printf("%lld\n", num);
}
int main()
{
	int t;
	scanf("%d", &t);

	while(t--)
		solve();
	return 0;
}

---

其他

1. Amity Assessment

• 背景 有两个 2 * 2 的网格（包含“A”、“B”、"C"三个字母以及一个空格 "X"），问你能否通过操作（两个网格都可以操作）变成两个相同的网格。

​

• 思路 只有两个网格（分别记为网格$X$，$Y$）都往一个方向（顺时针或逆时针）操作时才可能变为相同。
  我们可以把网格用字符串表示，即从左上角开始，顺时针拼接字符（空格可以忽略，对答案没影响）。把网格 $X$ 拼接成环，即在原字符串后再复制一遍字符串，如果其中包含迷宫 $Y$，则可以，否则不能。
  例如上图，网格 $X$ 为 “ABCABC”，网格 $Y$ 为 “BCA”，所以可以。
  
  
• 代码

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

int main()
{
    string b, e, b1, b2, e1, e2;
    cin >> b1 >> b2 >> e1 >> e2;

    swap(b2[0], b2[1]);//顺时针拼接字符串
    swap(e2[0], e2[1]);

    b = b1 + b2;
    e = e1 + e2;

    b.erase(b.find('X'), 1);
    e.erase(e.find('X'), 1);

    b += b;//拼接成环，表示整个操作过程
    if(b.find(e) != string::npos)//find函数在找不到指定值得情况下会返回string::npos
        puts("YES");
    else
        puts("NO");
    return 0;
}

---

2. hhh

笔记进度