C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1074 约瑟夫环 V2

题意

约瑟夫环,N-1e18,K-1000

思路

由于K远小于N,后面i大了之后某些时候不用取模,可以加速。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,k;
ll cur,t;
int main(){
cin>>n>>k;
cur=0;
for(ll i=2;i<=n;i+=t+1){
t=(i-cur)/k-1;
if(t<0) t=0;
if(i+t+1>n) t=n-i;
cur=(cur+(t+1)*k)%(i+t);
}
cur++;
cout<<cur<<endl;
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/2897/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!