手表网站欧米茄报价,iapp用网站做的APP无法加载,短视频网站开发,衡水网站开发报价Lark收藏了很多玩具。尽管她有很多玩具#xff0c;但她每次只喜欢玩一个。她决定玩哪个玩具#xff0c;把所有玩具放在她周围的一个圆圈里#xff0c;编号为 0 到 T-1 。然后#xff0c;她顺时针旋转#xff0c;去除第K个玩具#xff0c;直到剩下一个为止。这意味着她拿走…Lark收藏了很多玩具。尽管她有很多玩具但她每次只喜欢玩一个。她决定玩哪个玩具把所有玩具放在她周围的一个圆圈里编号为 0 到 T-1 。然后她顺时针旋转去除第K个玩具直到剩下一个为止。这意味着她拿走的第一个玩具是有编号的K−1。如果在这个仪式中移动了任何玩具Lark就会开始哭泣然后按照原来的顺序重新排列玩具。 今天Lark想让她的爸爸和她一起玩玩具。在Lark挑选的玩具中她的父亲当然有一个最喜欢的玩具当然也希望能选择那个特定的玩具。他应该把他最喜欢的玩具放在哪个位置以确保这就是他们最终玩的玩具
Input 输入是由2个整数组成 T和K,表示Lark拥有的玩具数量和在选择下一个要丢弃的玩具时跳跃长度。
Output 输出一个整数父亲需要放置他最喜欢的玩具的位置以供选择。Lark将在位置0 开始计数。
【数据范围】 1≤T≤10000000 ,1≤K≤1000000,K≤T
输入样例1 5 2 输出样例1 2
输入样例2 25 18 输出样例2 1
解析
我们采用倒推我们倒推出最后剩下的这个数字在最开始的数组中的位置。
剩下最后一个数字简称“它”的时候总个数为 1它的下标 pos0。 那么它在上一轮也是安全的总个数为 2它的下标 pos(0m)%2 解释在上一轮中它前面的数字即下标为 m-1 的数字被删走了因此它的下标是 m由于是环因此需要 %2 那么它在上上轮也是安全的总个数为 3它的下标 pos(((0m)%2)m)%3 那么它在上上上轮也是安全的总个数为 4它的下标 pos((((0m)%2)m)%3m)%4 ... 那么它在游戏开始的第一轮也是安全的总个数为 n它的下标就是最优位置即父亲需要放置他最喜欢的玩具的位置。
也就是说如果从下向上反推的时候假如它下一轮的下标为 pos那么当前轮次的下标就是 (posm) 当前轮次的人数。
一、暴力(超时)
#include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const int N1e710;
int n,m;
bool p[N];
signed main()
{ios;cinnm;int cntn;int k-1,falg0;while (1){k;if (!p[k%n]) falg;if (falgm){cnt--;p[k%n]1;if (!cnt){if (k%n) coutk%n;else cout0;break;}falg0;}}return 0;
}
二、递归
#include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const int N1e710;
int find(int n,int k)
{if (n1){return 0;}return (find(n-1,k)k)%n;
}
int n,k;
signed main()
{ios;cinnk;coutfind(n,k);return 0;
}
三、递推(根据二)
#include bits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
typedef pairint,int PII;
const int N1e710;
int find(int n,int k)
{int ans0;for (int i2;in;i) ans(ansk)%i;return ans;
}
int n,k;
signed main()
{ios;cinnk;coutfind(n,k);return 0;
}
