帮忙设计一个效率最高的算法～～～

撒法五

设f（x）＝2500000000－99999X，其中x在[0.25000]之间，想一个算法，让计算机尽可能少的枚举出所有使f（x）为完全平方数的x值

（注：此处强调的是算法的效率）

我现在想到的最少要枚举2700多次（已经缩掉近90％了，但还想减小工作量），不知有什么好的算法能够再减少些～～大家帮忙啦～

chsi

2700多次，对于现在的电脑来说可以忽略不计。

chsi

int  issqure(int   n)
{   
    int i =
1;
    for(;n>0;i+=2) n-=i;   
   
    return
0==n;   
}

撒法五

我举的的只是特例，要在计算器平台上做的。楼上的算法实在是。。。。。

撒法五

请不要想的太简单。。。。。想要缩掉90％的工作量需要很多的一番推导的

chsi

我的那个函数效率很高

chsi

性质1：完全平方数的末位数只能是0,1,4,5,6,9。
性质2：奇数的平方的个位数字为奇数，十位数字为偶数。
证明 奇数必为下列五种形式之一：
10a+1, 10a+3, 10a+5, 10a+7, 10a+9
分别平方后，得
(10a+1)^2=100+20a+1=20a(5a+1)+1
(10a+3)^2=100+60a+9=20a(5a+3)+9
(10a+5)^2=100+100a+25=20 (5a+5a+1)+5
(10a+7)^2=100+140a+49=20 (5a+7a+2)+9
(10a+9)^2=100+180a+81=20 (5a+9a+4)+1
综上各种情形可知：奇数的平方，个位数字为奇数1,5,9；十位数字为偶数。
性质3：如果完全平方数的十位数字是奇数，则它的个位数字一定是6；反之，如果完全平方数的个位数字是6，则它的十位数字一定是奇数。
证明 已知=10k+6，证明k为奇数。因为的个位数为6，所以m的个位数为4或6，于是可设m=10n+4或10n+6。则
10k+6=(10n+4)=100+(8n+1)x10+6
或 10k+6=(10n+6)=100+(12n+3)x10+6
即 k=10+8n+1=2(5+4n)+1
或 k=10+12n+3=2(5+6n)+3
∴ k为奇数。
推论1：如果一个数的十位数字是奇数，而个位数字不是6，那么这个数一定不是完全平方数。
推论2：如果一个完全平方数的个位数字不是6，则它的十位数字是偶数。
性质4：偶数的平方是4的倍数；奇数的平方是4的倍数加1。
这是因为 (2k+1)=4k(k+1)+1
(2k)=4
性质5：奇数的平方是8n+1型；偶数的平方为8n或8n+4型。
在性质4的证明中，由k(k+1)一定为偶数可得到(2k+1)是8n+1型的数；由为奇数或偶数可得(2k)为8n型或8n+4型的数。
性质6：平方数的形式必为下列两种之一：3k,3k+1。
因为自然数被3除按余数的不同可以分为三类：3m,3m+1, 3m+2。平方后，分别得
(3m)=9=3k
(3m+1)=9+6m+1=3k+1
(3m+2)=9+12m+4=3k+1
同理可以得到：
性质7：不能被5整除的数的平方为5k±1型，能被5整除的数的平方为5k型。
性质8：平方数的形式具有下列形式之一：16m,16m+1, 16m+4,16m+9。
除了上面关于个位数，十位数和余数的性质之外，还可研究完全平方数各位数字之和。例如，256它的各位数字相加为2+5+6=13，13叫做256的各位数字和。如果再把13的各位数字相加：1+3=4，4也可以叫做256的各位数字的和。下面我们提到的一个数的各位数字之和是指把它的各位数字相加，如果得到的数字之和不是一位数，就把所得的数字再相加，直到成为一位数为止。我们可以得到下面的命题：
一个数的数字和等于这个数被9除的余数。
下面以四位数为例来说明这个命题。
设四位数为，则
= 1000a+100b+10c+d
= 999a+99b+9c+(a+b+c+d)
= 9(111a+11b+c)+(a+b+c+d)
显然，a+b+c+d是四位数被9除的余数。
对於n位数，也可以仿此法予以证明。
关於完全平方数的数字和有下面的性质：
性质9：完全平方数的数字之和只能是0,1,4,7,9。
证明 因为一个整数被9除只能是9k,9k±1, 9k±2, 9k±3, 9k±4这几种形式，而
(9k)=9(9)+0
(9k±1)=9(9±2k)+1
(9k±2)=9(9±4k)+4
(9k±3)=9(9±6k)+9
(9k±4)=9(9±8k+1)+7
除了以上几条性质以外，还有下列重要性质：
性质10：为完全平方数的充要条件是b为完全平方数。
证明 充分性：设b为平方数，则
==(ac)
必要性：若为完全平方数，=，则
性质11：如果质数p能整除a，但p的平方不能整除a，则a不是完全平方数。
证明 由题设可知，a有质因数p，但无因数，可知a分解成标准式时，p的次方为1，而完全平方数分解成标准式时，各质因数的次方均为偶数，可见a不是完全平方数。
性质12：在两个相邻的整数的平方数之间的所有整数都不是完全平方数，即若
n^2 < k^2 < (n+1)^2
则k一定不是完全平方数。
性质13：一个正整数n是完全平方数的充分必要条件是n有奇数个因数(包括1和n本身)。

撒法五

额......利用这点性质我就不会来求助了...根本不够啊...数量级一大就不行了

撒法五

计算器里就算排掉90%都不够...唉...

撒法五

计算器里就算排掉90%都不够...唉.....还有chsi...能不能用中文解释下你的算法?我电脑编程语言不会的...

chsi

感觉还是要一个一个算，想不出别的什么方法。

h4x

我写的算法倒是能用
但是效率不高

1. 
   
2. C:\WINDOWS\system32\cmd.exe /c test
   
3. Found x=17284
   
4. Found x=14336
   
5. Found x=4641
   
6. Found x=1
   
7. Found x=0
   
8. Searched 50001
   
9. Hit any key to close this window...
   

复制代码

下面是C++代码

1. 
   
2. #include<iostream>
   
3. #include<cmath>
   
4. using namespace std;
   
5. 
   
6. int P = 0;
   
7. int Q = 25000;
   
8. unsigned long B = 2500000000L;
   
9. unsigned long A = 99999L;
   
10. 
    
11. int main()
    
12. {
    
13.         int n_min = (int)sqrt((float)(B - A*Q));
    
14.         int n_max = (int)sqrt((float)(B - A*P));
    
15. 
    
16.         long i;
    
17.         for(i=n_min; i<=n_max; i++)
    
18.                 if( (B - i*i) % A == 0 )
    
19.                         cout<< "Found x=" << (B - i*i)/A << endl;
    
20.        
    
21.         cout << "Searched " << i <<endl;
    
22.         return 0;
    
23. }
    

复制代码

囧。。Discuz!没有代码高亮 在这里喷一个  - -

h4x

其实也不错啦 - -。。
上次NOIP的时候 某题我写了个废品暴力搜索 搜了半个小时
然后把答案写成数组一交。。直接AC
囧rz..后来才知道原来大牛也都是交表AC的

xzxzxz

我记得VIJOS上有类似题。
　　1.个位数是2,3,7,8的整数一定不是完全平方数；
　　2.个位数和十位数都是奇数的整数一定不是完全平方数；
　　3.个位数是6，十位数是偶数的整数一定不是完全平方数；
　　4.形如3n+2型的整数一定不是完全平方数；
　　5.形如4n+2和4n+3型的整数一定不是完全平方数；
　　6.形如5n±2型的整数一定不是完全平方数；
　　7.形如8n+2, 8n+3, 8n+5, 8n+6,8n+7型的整数一定不是完全平方数；
　　8.数字和是2,3,5,6,8的整数一定不是完全平方数。
要不然可以用电脑算，然后打表。

h4x

VIJOS上面有这种题的话也够无聊的 - =。。
交表果然王道。。。