这几天遇到了一个难题，对给定的f(n) 当 n>=50025002 的时候，f(n)=n-5；当 n<50025002 的时候，f(n)=f(f(n+2005))。输入一个数， 范围相当的大啊 -2147483647<n<2147483647，求F（N）， 不要用函数嵌套， 因为数字大了以后， 嵌套的次数多了，超过内存限制或时间超时


==============================================================
added by HJin

1. problem statement at http://acm.nankai.edu.cn/p1002.html
2. modified your title so that it is more descriptive.

[此贴子已经被HJin于2007-7-18 1:19:43编辑过]

高精度吗?

用数组解决

搜索一下就能有很多资料了。

LS不对哦，别人都限定了-2147483647<n<2147483647

LZ是想不用递归吧（就是你说的嵌套，可以试着用迭代，效率好很多）。

想了很多方法都是一定范围内的数可以实现,但是数字很大以后就会得到错误的答案, 有能力的可以去http://acm.nankai.edu.cn/p1002.html看看, 希望AC的大鸟能给我份SOURCE CODE

你是初学ACM还是初学C++啊？初学C++就没必要做这种题了，初学ACM的话做做到是不错

还要谢你介绍了一个不错的OJ，以前不知道南开的OJ这么好（从设计上），应该弄的比较晚吧

#include <stdio.h>
#include <stdlib.h>

inline int mod(int a,int b)
{
    return a>=0?a%b:a%b+b;
}
int main()
{
    int n;
    while(scanf(\"%d\",&n)!=EOF){
        if(n>=50025002){
            printf(\"%d\n\",n-5);
        }
        else if(n>=0){
            printf(\"%d\n\",50024997+mod(n-1002,2000));
        }
        else {
            printf(\"%d\n\",50024997+mod(n+998,2000));
        }
    }
}

嘿嘿`
我刚加进来的
多多指教哈！

seems it is the math for an explicit formula of f(n) that makes this problem worth a point.

leeco:

(guess you are right --- found my mistake)

Is your result 100% correct? Seems that I have a math theorem:

N-5 <= f(n) < N+1995 if n <N, where N = 50025002.

[此贴子已经被作者于2007-7-18 1:23:16编辑过]

There is a lot of math involved here. Here is my attack, which
is accepted at http://acm.nankai.edu.cn/p1002.html

To compete for smaller source file size, I rewrote it as a .c file (accepted of course and but with no readability).

I don't know why the online judge said that my program needs 672kb memory while other people are using
just 32kb. Frankly, I don't think the following one line source code will need 672kb memory.

What is wrong here?

int main(){int n;while(scanf(\"%d\",&n)!=-1){while(n<50025002)n+=2000;printf(\"%d\n\",n-5);}return 0;}

===============================================================

(.cpp file)
#include <iostream>
using namespace std;

int f(int a, int b, int N, int n)
{
int temp = a - b;
while(n<N)
{
n+=temp;
}

return n-b;
}

int main()
{
int n;

while ( scanf("%d", &n) != EOF )
{
printf("%d\n", f(2005, 5, 50025002, n));
}

return 0;
}

[此贴子已经被作者于2007-7-18 7:16:36编辑过]