题意
约瑟夫环,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; }
|