qwb与整数对
Time Limit: 1 Sec Memory Limit: 128 MB
Description
qwb又遇到了一道数学难题,你能帮助他吗?
给出两个整数n和m,请统计满足0<a<b<n并且使得
(a2+b2+m)/(ab) 的结果是整数的整数对(a,b)的个数。
Input
本题包含多组测试例 。当测试例数据是n=m=0时,表示输入结束。(测试例数量<6000)
每个测试例一行,是两个整数n和m。输入保证0≤n≤1000,-20000<m<20000。
Output
对每个测试例,输出测试例的编号(Case X:Y)
以及满足上述要求的整数对(a,b)的个数,输出格式如样例输出所示。
Sample Input
10 1
20 3
30 4
0 0
Sample Output
Case 1: 2
Case 2: 4
Case 3: 5
分析:枚举a,b及a*b的倍数就好了呢;
开个1000*40000的数组会MLE,只能离线查询了;
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <cassert>
#include <ctime>
#include<unordered_map>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define sys system("pause")
const int maxn=4e4+;
const int N=5e2+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p%mod;p=p*p%mod;q>>=;}return f;}
int n,m,k,t,ret[maxn],ans[maxn],cnt;
vector<pii>qu[maxn];
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==)break;
qu[n].pb(mp(m,++cnt));
}
rep(i,,)
{
for(j=;j<qu[i].size();j++)
{
ans[qu[i][j].se]=ret[qu[i][j].fi+];
}
rep(j,,i-)
{
int t;
if(i*i+j*j<)t=(i*i+j*j-)/(i*j);
else t=(i*i+j*j-+i*j-)/(i*j);
for(k=(i*i+j*j+)/(i*j);t<=k;t++)
{
int pos=t*i*j-i*i-j*j;
ret[pos+]++;
}
}
}
rep(i,,cnt)printf("Case %d: %d\n",i,ans[i]);
return ;
}