首页 > 代码库 > qwb与整数对
qwb与整数对
qwb与整数对
Time Limit: 1 Sec Memory Limit: 128 MBDescription
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 120 330 40 0
Sample Output
Case 1: 2Case 2: 4Case 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+10;const int N=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}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==0&&m==0)break; qu[n].pb(mp(m,++cnt)); } rep(i,1,1000) { for(j=0;j<qu[i].size();j++) { ans[qu[i][j].se]=ret[qu[i][j].fi+20000]; } rep(j,1,i-1) { int t; if(i*i+j*j<20000)t=(i*i+j*j-20000)/(i*j); else t=(i*i+j*j-20000+i*j-1)/(i*j); for(k=(i*i+j*j+20000)/(i*j);t<=k;t++) { int pos=t*i*j-i*i-j*j; ret[pos+20000]++; } } } rep(i,1,cnt)printf("Case %d: %d\n",i,ans[i]); return 0;}
qwb与整数对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。