模板--HihoCoder--1296--约瑟夫问题

HihoCoder--1296--约瑟夫问题

代码一：超时

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL n,k;
LL solve(){LL ret=0;for(int i=2;i<=n;i++)ret=(ret+k)%i;return ret;
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&k);printf("%lld\n",solve());}return 0;
} 

代码二：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL n,k;
LL Josephus(LL n,LL k){if(n==1)	return 0;else if(n<k){LL ans=0;for(int i=2;i<=n;i++)ans=(ans+k)%i;return ans;}LL ans=Josephus(n-n/k,k);if(ans<n%k)	ans=ans-n%k+n;else	ans=ans-n%k+(ans-n%k)/(k-1);return ans; 
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&k);printf("%lld\n",Josephus(n,k));}return 0;
}