T1 - 调整座位
TooY0ung 的思路
不知道同学们做着难不难，我反正是一分钟秒了。
其实完全没有必要全排列，因为 k<=n，实际上你只需要每次移动一位就行了。
比如第一次是 : 1234，下一次就输出 2341。
这里的写法也是各显神通，你可以直接算余数，也可以像我们之前讲的一样复制一遍。
TooY0ung 的满分余数写法
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int k, n, a[110];
int main()
{
freopen("seat.in", "r", stdin);
freopen("seat.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 0; i < k; i++)
{
for(int j = 1; j <= n; j++)
cout << (j + i - 1) % n + 1<< " ";
cout << "\n";
}
return 0;
}
TooY0ung 的复制写法
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int k, n, a[210];
int main()
{
freopen("seat.in", "r", stdin);
freopen("seat.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 1; i <= n; i++)
{
a[i] = i;
a[i + n] = i;
}
for(int i = 1; i <= k; i++)
{
for(int j = i; j <= i + n - 1; j++)
{
cout << a[j] << " ";
}
cout << "\n";
}
return 0;
}
T2 - 三点定位
TooY0ung 的思路
在没改数据范围之前，我已经写了一半解方程代码了。
突然改了数据，同学们也直呼良心。
在 −d1 ～ d1 直接枚举 x 和 y 就行了，反正数据范围很小。
我不建议多费脑细胞思考类似于 x 固定了， d1 也知道，y 就算一算这种没意义的东西。
全都交给 c++ 循环不好吗？反正也不会超时。
TooY0ung 的满分代码
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int main()
{
freopen("point.in", "r", stdin);
freopen("point.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int x1, y1, d1;
int x2, y2, d2;
int x3, y3, d3;
cin >> x1 >> y1 >> d1;
cin >> x2 >> y2 >> d2;
cin >> x3 >> y3 >> d3;
for(int dx = -d1; dx <= d1; dx++)
{
int x = x1 + dx;
for(int dy = -d1; dy <= d1; dy++)
{
int y = y1 + dy;
if(abs(x - x1) + abs(y - y1) != d1) continue;
if(abs(x - x2) + abs(y - y2) != d2) continue;
if(abs(x - x3) + abs(y - y3) == d3)
{
cout << x << " " << y << "\n";
return 0;
}
}
}
return 0;
}
T3 - 隔代因子
TooY0ung 的思路
首先我们要先搞懂至少 k 代因子的含义。
题目中说，一个数的真因子是指小于它且能整除它的数，这个也是 至少1代因子。
那么至少 2 代因子就是存在中间因子 c，使得 b−>c−>n。
你会发现，这个可以看成图上的链，长度为 3。
那么至少 k 代因子是不是就是存在一个长度为 k+1 的因子链 ：
b−>c1−>c2−>.....−>ck−1−>n。
所以，一个因子 b 是 n 的 “至少 k 代因子”，
就是 b 到 n 的最长因子链长度 ≥ k+1。
因子怎么算呢？你的数学老师肯定教过你质因数分解吧。
一个数字 n，我们可以可以对它进行分解质因数。
即，n=p1e1 * p2e2 * p3e3 * ... * pmem。
其中，p1,p2,p3,....,pm 是质数，e1,e2,e3,....,em 是对应的指数。
那么 n 的任何一个真因子 d 都可以表示为类似于质因数分解的形式，即：
d=p1a1 * p2a2 * .....* pmam。
其中需要满足任意的 0<=ai<=ei，且至少有一个 ai<ei，因为如果都等于，就不是真因子。
那么指数和本道题目有什么关系呢？
不妨可以举个例子：
设 n=12=22∗31，真因子 d=3=20∗31。
此时的最长因子链应该是：3−>6−>12，总长度为 3。
为什么中间可以加入 6 和 12 两个数呢？
你不难发现：6=21∗31，12=22∗31。
换言之，就是之前对于质因数分解中，2 的指数我们还有两个可以使用。
那么有多少个“指数差”，是不是就可以加入多少个真因子。
我们定义“指数差”为，每个质数的指数在 n 和 d 中的差。
设 ti=ei−ai。
则 sum=t1+t2+....+tm。
回到刚刚的例子中，sum=2+0=2，正好等于链长 −1。
所以，最长因子链的长度 = sum+1。
回顾我们刚刚说的，一个因子 b 是 n 的 “至少 k 代因子”，就是 b 到 n 的最长因子链长度 ≥ k+1。
就是 sum+1 >= k+1，那就是 sum>=k。
接下来不就是分解质因数了吗？
全班唯一一个比赛期间通过的同学-胡宇泽
#include<bits/stdc++.h>
using namespace std;
int dai(long long x){
int cnt=0;
for(long long p=2;p*p<=x;p++){
while(x%p==0){
cnt++;
x/=p;
}
}
if(x>1)cnt++;
return cnt;
}
int main(){
freopen("factor.in","r",stdin);
freopen("factor.out","w",stdout);
long long n,k;
cin>>n>>k;
int ans=0;
for(long long d=1;d*d<=n;d++){
if(n%d==0){
long long m1=d;
long long m2=n/d;
if(m1<n&&dai(n/m1)>=k) ans++;
if(m2!=m1&&m2<n&&dai(n/m2)>=k) ans++;
}
}
cout<<ans;
return 0;
}
## T1 - 调整座位
### TooY0ung 的思路
不知道同学们做着难不难，我反正是一分钟秒了。
其实完全没有必要全排列，因为 $k <= n$，实际上你只需要每次移动一位就行了。
比如第一次是 : $1234$，下一次就输出 $2341$。
这里的写法也是各显神通，你可以直接算余数，也可以像我们之前讲的一样复制一遍。
### TooY0ung 的满分余数写法
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int k, n, a[110];
int main()
{
freopen("seat.in", "r", stdin);
freopen("seat.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 0; i < k; i++)
{
for(int j = 1; j <= n; j++)
cout << (j + i - 1) % n + 1<< " ";
cout << "\n";
}
return 0;
}
```
### TooY0ung 的复制写法
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int k, n, a[210];
int main()
{
freopen("seat.in", "r", stdin);
freopen("seat.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 1; i <= n; i++)
{
a[i] = i;
a[i + n] = i;
}
for(int i = 1; i <= k; i++)
{
for(int j = i; j <= i + n - 1; j++)
{
cout << a[j] << " ";
}
cout << "\n";
}
return 0;
}
```
## T2 - 三点定位
### TooY0ung 的思路
在没改数据范围之前，我已经写了一半解方程代码了。
突然改了数据，同学们也直呼良心。
在 $-d1$ ～ $d1$ 直接枚举 $x$ 和 $y$ 就行了，反正数据范围很小。
我不建议多费脑细胞思考类似于 $x$ 固定了， $d1$ 也知道，$y$ 就算一算这种没意义的东西。
全都交给 $c++$ 循环不好吗？反正也不会超时。
### TooY0ung 的满分代码
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e6 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
int main()
{
freopen("point.in", "r", stdin);
freopen("point.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int x1, y1, d1;
int x2, y2, d2;
int x3, y3, d3;
cin >> x1 >> y1 >> d1;
cin >> x2 >> y2 >> d2;
cin >> x3 >> y3 >> d3;
for(int dx = -d1; dx <= d1; dx++)
{
int x = x1 + dx;
for(int dy = -d1; dy <= d1; dy++)
{
int y = y1 + dy;
if(abs(x - x1) + abs(y - y1) != d1) continue;
if(abs(x - x2) + abs(y - y2) != d2) continue;
if(abs(x - x3) + abs(y - y3) == d3)
{
cout << x << " " << y << "\n";
return 0;
}
}
}
return 0;
}
```
## T3 - 隔代因子
### TooY0ung 的思路
首先我们要先搞懂至少 $k$ 代因子的含义。
题目中说，一个数的真因子是指小于它且能整除它的数，这个也是 **至少1代因子**。
那么至少 $2$ 代因子就是存在中间因子 $c$，使得 $b -> c -> n$。
你会发现，这个可以看成图上的链，长度为 $3$。
那么至少 $k$ 代因子是不是就是存在一个长度为 $k+1$ 的因子链 ：
$b -> c_1 -> c_2 -> ..... -> c_{k-1} -> n$。
所以，一个因子 $b$ 是 $n$ 的 “至少 $k$ 代因子”，
就是 $b$ 到 $n$ 的最长因子链长度 ≥ $k+1$。
因子怎么算呢？你的数学老师肯定教过你质因数分解吧。
一个数字 $n$，我们可以可以对它进行分解质因数。
即，$n = p_1^{e_1}$ * $p_2^{e_2}$ * $p_3^{e_3}$ * ... * $p_m^{e_m}$。
其中，$p_1,p_2,p_3,....,p_m$ 是质数，$e_1,e_2,e_3,....,e_m$ 是对应的指数。
那么 $n$ 的任何一个真因子 $d$ 都可以表示为类似于质因数分解的形式，即：
$d = p_1^{a_1}$ * $p_2^{a_2}$ * .....* $p_m^{a_m}$。
其中需要满足任意的 $0 <= a_i <= e_i$，且至少有一个 $a_i < e_i$，因为如果都等于，就不是真因子。
那么指数和本道题目有什么关系呢？
不妨可以举个例子：
设 $n = 12 = 2^2 * 3^1$，真因子 $d = 3 = 2^0 * 3^1$。
此时的最长因子链应该是：$3->6->12$，总长度为 $3$。
为什么中间可以加入 $6$ 和 $12$ 两个数呢？
你不难发现：$6 = 2^1*3^1$，$12 = 2^2*3^1$。
换言之，就是之前对于质因数分解中，$2$ 的指数我们还有两个可以使用。
那么有多少个“指数差”，是不是就可以加入多少个真因子。
我们定义“指数差”为，每个质数的指数在 $n$ 和 $d$ 中的差。
设 $t_i = e_i - a_i$。
则 $sum = t_1 + t_2 + .... + t_m$。
回到刚刚的例子中，$sum = 2 + 0 = 2$，正好等于链长 $-1$。
所以，最长因子链的长度 = $sum + 1$。
回顾我们刚刚说的，一个因子 $b$ 是 $n$ 的 “至少 $k$ 代因子”，就是 $b$ 到 $n$ 的最长因子链长度 ≥ $k+1$。
就是 $sum + 1$ >= $k + 1$，那就是 $sum >= k$。
接下来不就是分解质因数了吗？
## 全班唯一一个比赛期间通过的同学-胡宇泽
```cpp
#include<bits/stdc++.h>
using namespace std;
int dai(long long x){
int cnt=0;
for(long long p=2;p*p<=x;p++){
while(x%p==0){
cnt++;
x/=p;
}
}
if(x>1)cnt++;
return cnt;
}
int main(){
freopen("factor.in","r",stdin);
freopen("factor.out","w",stdout);
long long n,k;
cin>>n>>k;
int ans=0;
for(long long d=1;d*d<=n;d++){
if(n%d==0){
long long m1=d;
long long m2=n/d;
if(m1<n&&dai(n/m1)>=k) ans++;
if(m2!=m1&&m2<n&&dai(n/m2)>=k) ans++;
}
}
cout<<ans;
return 0;
}
```
