csuoj 1337: 搞笑版费马大定理

2022-09-18 20:42:30

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1337

1337: 搞笑版费马大定理

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 625 Solved: 301
[Submit][Status][Web Board]

Description

费马大定理：当n>2时，不定方程an+bn=cn没有正整数解。比如a3+b3=c3没有正整数解。为了活跃气氛，我们不妨来个搞笑版：把方程改成a3+b3=c3，这样就有解了，比如a=4, b=9, c=79时43+93=793。

输入两个整数x, y, 求满足x<=a,b,c<=y的整数解的个数。

Input

输入最多包含10组数据。每组数据包含两个整数x, y（1<=x,y<=108）。

Output

对于每组数据，输出解的个数。

Sample Input

Sample Output

Case 1: 0

Case 2: 2

Case 3: 16

HINT

分析：

因为C最大为10^8 ，所以 a , b 最大可以设置为1000 ，( a ^ 3 + b ^ 3 ) 最后一位肯定是3 ，这个条件可以提速，另外其值除以10 之后肯定是在x 和 y 范围内的，这个条件也可以提速。

AC代码：

 #include <stdio.h>

 #include <algorithm>

 #include <iostream>

 #include <string.h>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <set>

 #include <map>

 #include <list>

 #include <iomanip>

 #include <vector>

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #pragma warning(disable:4786)

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAX =  + ;

 const double eps = 1e-;

 const double PI = acos(-1.0);

 int main()

 {

   int x , y , a , b , c , first = ;

   while(~scanf("%d%d",&x , &y))

   {

         int ans = ;

         for(a = x;a <=  && a <= y;a ++)

             for(b = x;b <=  && b <= y;b ++)

             {

                 int s = a * a * a + b * b * b;

                 if(s %  != )

                     continue;

                 c = s / ;

                 if(c >= x && c <= y)

                     ans ++;

             }

          printf("Case %d: %d\n", first ++, ans);

   }

   return ;

 }

码农公寓