csuoj 1337: 搞笑版费马大定理

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 = 1000 + 10;
const double eps = 1e-8;
const double PI = acos(-1.0);

int main()
{
  int x , y , a , b , c , first = 1;
  while(~scanf("%d%d",&x , &y))
  {
        int ans = 0;
        for(a = x;a <= 1000 && a <= y;a ++)
            for(b = x;b <= 1000 && b <= y;b ++)
            {
                int s = a * a * a + b * b * b;
                if(s % 10 != 3)
                    continue;
                c = s / 10;
                if(c >= x && c <= y)
                    ans ++;
            }
         printf("Case %d: %d
", first ++, ans);
  }
  return 0;
}