UVa 1394 - and Then There Was One(约瑟夫数论)

数论问题, n 个人围成环,每点 m 个就删掉点到的那个,问最后剩下人的编号。
递推公式为 f [ i ] = ( f [ i − 1 ] + m ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
const int maxn=10010;
int f[maxn];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)&&n){
f[1]=0;
for(int i=2;i<=n;++i) f[i]=(f[i-1]+m)%i;
int ans=(1+f[n])%n;
if(ans<=0) ans+=n;
printf("%d\n",ans);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。