首页技术正文

csuoj 1337: 搞笑版费马大定理

开发者树潼技术 2022年11月16日

0 收藏 897 点赞 3,125 浏览 1150 个字

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

1 10
1 20
123 456789

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 ;
 }