UVa 1394 - And Then There Was One（约瑟夫数论）

发表于 分类于 ， ， Disqus：

数论问题， 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博客，格式可能有所偏差。 **

相关文章