玩游戏
玩游戏
玩游戏(game)
题目背景
x在玩游戏。
题目描述
x有一个长度为\(n\)的序列\(a\)和一个长度为\(n\)的序列\(x\)，序列\(x\)正好是\(1\sim n\)的排列。
在\(0\)轮中，序列\(a_i=i，i\in [1，n]\)。
每下一轮，X都会执行一次操作。在最后一轮中将\(a_i\)替换为\(a_{x_i}\)。
同时，x还要求恰好在\(m\)轮次中排序\(a_i=i，i\in [1，n]\)，即与\(0\)轮次处于同一状态，且没有\(t(1\le tm)\)，这样在第一轮。
现在X要求你构造一个组合序列\(x\)。如果没有合法的序列\(x\)，输出\(-1\)。
因为提问者懒得写spj，所以X想让你输出字典顺序最小的序列\(x\)。
输入格式
一行，两个正整数\(n，m\)。
输出格式
一行数字，即满足要求的最小字典顺序的序列。
样例
样例输入 1
8 7
样例输出 1
1 3 4 5 6 7 8 2
样例输入 2
8 8
样例输出 2
2 3 4 5 6 7 8 1
样例输入 3
8 9
样例输出 3
-1
数据范围与提示
对于\(20\%\)，\ (1 \ le n \ le 10 3，1 \ le m \ le 10 7 \)
此外，对于\(10\%\)，\(m=1\)的数据。
对于\(100\%\)，\ (1 \ le n \ le 3 \乘以10 ^ 6，1 \ le m \ le 10 {14} \)
solution
题解
研究发现，如果一个数经过几轮后回到自身，那么这个数和过程中的那些数可以形成一个大小为\(b_i\)的环。
因此，这个问题就变成了构造一个任意长度、n和m的最小公倍数的序列b，并最小化它的字典顺序。
也就是满足：
\(1\le k，b_i\le n\)
\(b_1 b_2 b_3 \cdots b_k=n\)
\(\operatorname{lcm}(b_1，b_2，b_3，\cdots，b_k)=m\)
在满足\(1，2，3\)的前提下，字典顺序最小。
因此，我们可以把\(m\)分解成素因子，把相同基数的数相乘，让这些数成为数列\(b\)。如果没有足够的\(n\)，我们可以补足\(1\)。
周期越大，越晚。当是周期的转折时，把\(t\)放在\(t b_i-1\)之后，可以证明此时字典顺序最小。
std
#包括牡蛎
#includecstdio
#包括算法
使用命名空间标准；
int n，p，q=1，cnt
长长m，ans[20]，和；
int main()
{
scanf(‘%d%lld ‘，n，m)；
for(long long I=2；I * I=m；(一)
{
if(m%i==0) p，ans[p]=1；
否则继续；
while(m%i==0)
{
ans[p]*=I；
m/=I；
}
sum=ans[p]；
}
if(m！=1)
{
ans[p]=m；
sum=ans[p]；
}
if(nsum)
{
printf(‘-1 \ n ‘)；
返回0；
}
sort(ans 1，ans P1)；
for(int I=1；I=n；(一)
{
if(I=n-和)
{
printf(“% d”，I)；
继续；
}
碳纳米管；
if(cnt==ans[q])
{
CNT=0；
printf(‘%lld ‘，I-ans[q]1)；
q；
}
else printf(‘%d ‘，I ^ 1)；
}
返回0；
}
后话
吐槽
思维简单，代码容易写，没有癌症的小问题和新鲜问题。
总结
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/74737.html