UVALive 6862 Triples （找规律暴力）

Triples

题目链接：

http://acm.hust.edu.cn/vjudge/contest/130303#problem/H

Description

http://7xjob4.com1.z0.glb.clouddn.com/4c05ed01e62e808388fc90e37554d588

Input

The input file contains several test cases, each of them as described below. The first line contains the value of m and the second line contains the value of n.

Output

For each test case, the result will be written to standard output, on a line by itself.

Sample Input

``` 85 95 ```

Sample Output

``` 8128 ```

Source

2016-HUST-线下组队赛-4
##题意：求有多少个三元组(x,y,z)满足 0<=x<=y<=z<=m 且 x^j + y^j = z^j.
##题解：由于n和m的数据都非常小，稍微打一下表就可以发现 j > 2 的时候不存在满足条件的三元组. upd：实际上，上述表述为[费马大定理](http://baike.baidu.com/link?url=Ap0jvXEvOF9go2DTQ7LieopZRcrkcECDceCIu4VequB0IE9Bo3d8IC6gNq0yYnHmLDpfB9BQrWJRyS4xx8QYS9Yx7Lv0qJ_LvQifKep4zNe) x=0时：y = z ∈ [0, m]. 故有 (m+1) * (n-1) 个解. j=2时：暴力求一下即可.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define maxn 101000 #define inf 0x3f3f3f3f #define mod 1000000007 #define mid(a,b) ((a+b)>>1) #define eps 1e-8 #define IN freopen("in.txt","r",stdin); using namespace std;

int solve(int m) {
int cnt = 0;
for(LL i=1; i<=m; i++) {
for(LL j=i; j<=m; j++) {
LL x = ii + jj;
for(LL k=0; k<=m; k++) {
if(k*k == x) {
//printf("%d %d %d ",i,j,k);
cnt++;
break;
}
}
}
}
return cnt;
}

int main()
{
//IN;

int m,n;
while(scanf("%d %d", &m,&n) != EOF)
{
    int ans = solve(m) + (m+1)*(n-1);

    printf("%d
", ans);
}

return 0;

}

UVALive 6862 Triples （找规律 暴力）