玩游戏
玩游戏
玩游戏(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