[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 L: qwb与整数对 [离线]【思维】

2017-06-03 02:55:21 Tabris_ 阅读数：656

博客爬取于2020-06-14 22:40:11
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849794

题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=11
——————————————————————————————————————————
Problem L: qwb与整数对
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 171 Solved: 18
[Submit][Status][Web Board]
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
——————————————————————————————————————————

在线的复杂度实在不科学

看dalao离线做了,我也做了下

离线之后n^2枚举到每个位置计算贡献的时候类似筛法只要找(i*j)的倍数就好了

然后记下这个时候的值询问,满足n的情况就ans++

感觉没有代码直观啊.

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

int n[6666],m[6666],ans[6666];
vector<int>vc[44444];

int main(){
    for(int i=1;~scanf("%d%d",&n[i],&m[i])&&(n[i]||m[i]);i++){
        vc[m[i]+20000].push_back(i);
    }
    for(int i=1;i<=1000;i++){
        for(int j=i+1;j<=1000;j++){
            int x=(i*j)-(i*i+j*j)%(i*j);
            for(int k=x;k<=20000;k+=i*j){
                int vcz=vc[k+20000].size();
                for(int u=0;u<vcz;u++){
                    if(n[vc[k+20000][u]]>j)
                        ans[vc[k+20000][u]]++;
                }
            }
            for(int k=x-i*j;k>=-20000;k-=i*j){
                int vcz=vc[k+20000].size();
                for(int u=0;u<vcz;u++){
                    if(n[vc[k+20000][u]]>j)
                        ans[vc[k+20000][u]]++;
                }
            }
        }
    }

    for(int i=1;(n[i]||m[i]);i++)  printf("Case %d: %d\n",i,ans[i]);

    return 0;
}