[51nod1074]约瑟夫环V2

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。

Input:

2个数N和K，表示N个人，数到K出列。\((2 <= N <= 10^{18}, 2 <= K <= 1000)\)

Output:

最后剩下的人的编号

my solution:暴力打表得出规律：\(f[n]=(f[n-1]+k)%n\)注意这个式子，因为k远远小于n所以，我们可以将式子转化为\((f[n+w]=f[n]+k*w)%(n+w)\),但是注意不能连续实际模两次，否则答案会有误

因此我们\(w=(i-ans)/k+1\),这样保证了<1>最多一次运算会有一次实际取模，<2>保障每次n至少加1，不会死循环

实际上操作我们将ans初始化为0，最后的答案加1，因为只有在区间\((1,n)\)中\(f[i]=(f[i-1]+k)%i\)才成立

复杂度\(O(klogn)\)不会分析

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

long long n,k;

int main(){

   cin>>n>>k;

   long long ans=0;

   for(long long i=1;i<=n;){

   long long w=(i-ans)/k+1;

   if(w+i>n)w=n-i;

   if(w==0)break;

   ans=(ans+w*k)%(w+i);

   i+=w;

 }

   cout<<ans+1;

   return 0;

}

//code from 本机房巨佬

巴特西

[51nod1074]约瑟夫环V2

最新文章

热门文章