首页 > 代码库 > [2017浙工大之江学院决赛 L] qwb与整数对(离线,筛)
[2017浙工大之江学院决赛 L] qwb与整数对(离线,筛)
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=11
这题不会,看了柠檬巨的题解才知道可以筛出来。
枚举a、b,然后求下m最小能是多少,可以满足原式为整数。可以用(a*b)-(a*a+b*b)%(a*b)求。然后在m的基础上算上a*b的倍数再更新到对应case上即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 6666; 5 const int maxm = 44444; 6 const int Q = 20000; 7 int n[maxn], m[maxn], ret[maxn]; 8 vector<int> id[maxm]; 9 10 int main() { 11 // freopen("in", "r", stdin); 12 for(int i = 1; ~scanf("%d%d",&n[i],&m[i]) && (n[i]||m[i]); i++) { 13 id[m[i]+Q].push_back(i); 14 } 15 for(int a = 1; a <= 1000; a++) { 16 for(int b = a+1; b <= 1000; b++) { 17 int M = (a*b)-(a*a+b*b)%(a*b); 18 for(int t = 0; M+t*(a*b) <= Q; t++) { 19 for(int i = 0; i < id[M+t*(a*b)+Q].size(); i++) { 20 if(b < n[id[M+t*(a*b)+Q][i]]) ret[id[M+t*(a*b)+Q][i]]++; 21 } 22 } 23 for(int t = 1; M-t*(a*b) >= -Q; t++) { 24 for(int i = 0; i < id[M-t*(a*b)+Q].size(); i++) { 25 if(b < n[id[M-t*(a*b)+Q][i]]) ret[id[M-t*(a*b)+Q][i]]++; 26 } 27 } 28 } 29 } 30 for(int i = 1; n[i]||m[i]; i++) { 31 printf("Case %d: %d\n", i, ret[i]); 32 } 33 return 0; 34 }
[2017浙工大之江学院决赛 L] qwb与整数对(离线,筛)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。