前言
数论比想象中重要。
第一题
题目： B - Practical Computing (atcoder.jp)
题意：
给一个整数n，输出前n行杨辉三角。
输入格式
输入仅包含一个整数n。
输出格式
输出前n行杨辉三角。
数据范围
1 ≤ N ≤ 30
N是一个整数。
输入样例：
5输出样例：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1思路：
- 简单模拟即可。
代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
int a[35][35];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)a[i][1] = 1;
cout << 1 << endl;
for (int i = 2; i <= n; ++i)
{
cout << 1 << " ";
for (int j = 2; j <= i; ++j)
{
a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
第二题
题目： C - K Swap (atcoder.jp)
题意：
给我们两个整数n和k，可以进行任意次交换，每次只能交换第i个数和第i+k个数。问是否可以将整个数列通过交换变为上升序列。
输入格式
输入第一行是两个整数n和k。
第二行是n个整数。
输出格式
如果可以通过交换得到上升数列，输出 Yes ，否则输出 No 。
数据范围
2 ≤ N ≤ 2 × 105
1 ≤ K ≤ N−1
1 ≤ ai ≤ 109
输入样例：
5 3
3 4 1 3 4输出样例：
No思路：
- 由于我们只能交换距离为k的两个数，所以可以将整个数列分为k个子序列，每个序列的开头依次是a1到ak。将所有子序列由小到大排序，然后将k个序列依次交叉排好，看整个数列是否有序即可。
代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, k;
vector<int>v[N];
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i)cin >> a[i];
if (k == 1)
{
cout << "Yes" << endl;
return 0;
}
//将整个数列分为k个子序列
for (int i = 1; i <= k; ++i)
{
int j = i;
while (j <= n)
{
v[i].push_back(a[j]);
j += k;
}
//对每个子序列进行升序排序
sort(v[i].begin(), v[i].end());
}
//将k个子序列依次交叉排好。
//例如序列一：[1，2,3]，序列二：[4,5,6]，序列三：[7,8,9]
//则排好后数列为：1,4,7,2,5,8,3,6,9
int b[N],j=1;
for (int i = 0; i < v[1].size(); ++i)
{
for (int h = 1; h <= k; ++h)
{
if (i >= v[h].size())break;
b[j++] = v[h][i];
}
}
//判断整个数列是否有序。
for (int i = 1; i < n; ++i)
{
if (b[i] > b[i + 1])
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
第三题-赛后补题
题目： D - Together Square (atcoder.jp)
题意:
给定一个整数n，从1到n中找到两个整数i和j，使得i*j可以表示某个整数的平方。问最多可以找到多少不同的组合。[1,4]和[4,1]视为两种不同的组合。
输入格式
输入只有一个整数n。
输出格式
输出一个整数。
数据范围
1 ≤ N ≤ 2×105
输入样例：
输出一行n个整数，两个整数之间用空格间隔。
数据范围
1≤N≤ 2×105
输入样例：
254输出样例：
896思路：
- 详见此文，解释的很好。
- 本题的核心点在于，令f(i)表示i因子中最大的平方数，如果
i*j是平方数，那么一定满足(i*j) / (f(i)*f(j))是平方数。 - 由上述性质推导出当
i*j是平方数时，i/f(i)一定等于j/f(j)，可以证明这是一个充要条件。进而只要找到每个i/f(i)可以由多少个i转化而来即可。因为无论i是否等于j，只要i/f(i)等于j/f(j)，那么i*j就是平方数。我们用cnt[k]来记录i可以由多少个i/f(i)转化而来，那么答案就是所有cnt[i]的平方和。 - 数论题就很离谱，往往看题解都看不懂。
代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
bool st[N];//标记是否为平方数
vector<int>v[N];//v[i]存i的因数，包括1和n
int cnt[N];//cnt[i]表示符合i==k/f(k)==j/f(j)的数量
int main()
{
int n;
cin >> n;
//标记1~n中所有的平方数
for (int i = 1; i * i <= n; ++i)st[i * i] = true;
//记录每个数的因子
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; j += i)v[j].push_back(i);
for (int i = 1; i <= n; ++i)
{
int f = 0;
for (int j = 0; j < v[i].size(); ++j)
if (st[v[i][j]])f = v[i][j];//找到所有因子中最大的平方数
//cnt[i]记录每个i可以由多少个j/f(j)转化而来
cnt[i / f]++;
}
int res = 0;
//因为只要任意两个数，只要满足i/f(i)的值相等，那么就可以组合为平方数，所以答案是每个cnt[i]的平方
for (int i = 1; i <= n; ++i)res += (cnt[i] * cnt[i]);
cout << res;
return 0;
}
