hdu4279 找规律+小想法
规律 想法
2023-09-11 14:13:59 时间
题意:
蛋疼的题意,最后是泽神给我讲的题意,题意是对于一个数来说,如果他不能整除另一个数同时他和另一个数非互质,那么另一个数就是这个数的特别数,如10 的特别数有 4 6 8三个,同时题目还定义,有奇数个特别数的数是真数,现在给你一个范围,问你有多少个数字是真数.
蛋疼的题意,最后是泽神给我讲的题意,题意是对于一个数来说,如果他不能整除另一个数同时他和另一个数非互质,那么另一个数就是这个数的特别数,如10 的特别数有 4 6 8三个,同时题目还定义,有奇数个特别数的数是真数,现在给你一个范围,问你有多少个数字是真数.
思路:
先打表,看下真实数的规律,假如当前数字是a,真实数其实就是6 到 a之间偶数的个数 + 奇数的平方数(如 9,25,49..) - 偶数的平方数(16 ,36 ,64..)
就是 : a / 2 - 2 + Sqrt(a) % 2 .
因为如果Sqrt(a)是奇数奇数平方数就比偶数平方数多1,否则相等,所以直接+ Sqrt(a) % 2,还有一点就是sqrt()对于__int64会失精度,所以用二分去找sqrt();
所以最后答案就是:
y / 2 - 2 + Sqrt(y) % 2 - ((x - 1) / 2 - 2 + Sqrt(x - 1) % 2 )
注意 x=1 和 x = 2的情况处理下,不然会错...下面是打表代码 和 AC代码
AC代码:
#include<stdio.h> __int64 max_ = 3037000499; __int64 Sqrt(__int64 num) { __int64 low ,mid ,up; low = 1 ,up = num; if(up > max_) up = max_; __int64 mk = 0; while(low <= up) { mid = (low + up) / 2; if(mid * mid > num) { up = mid - 1; } else { low = mid + 1; mk = mid; } } return mk; } int main () { __int64 x ,y ,t; scanf("%I64d" ,&t); while(t--) { scanf("%I64d %I64d" ,&x ,&y); __int64 xx = (x-1) / 2 - 2 + Sqrt(x-1) % 2; __int64 yy = y / 2 - 2 + Sqrt(y) % 2; if(x == 1 || x == 2) xx = 0; if(y == 1) yy = 0; printf("%I64d\n" ,yy - xx); } return 0; } 打表代码:
#include<stdio.h> int main () { int sss = 0; for(int i = 1 ;i <= 100 ;i ++) { int now = i ,sum = 0; for(int j = 2 ;j < i ;j ++) { if(i % j == 0)continue; for(int ii = 2 ;ii <= j ;ii ++) if(i % ii == 0 && j % ii == 0) { sum++; break; } } if(sum % 2) printf("%d " ,i); } getchar(); getchar(); getchar(); return 0; }
相关文章
- hdu4279 找规律+小想法
- HDU 5402 Travelling Salesman Problem (模拟 有规律)(左上角到右下角路径权值最大,输出路径)
- 信号频谱能量收敛规律
- 93个不规律动词(DIY脑图)
- LightOJ 1010 Knights in Chessboard (规律)
- HDU 1165 Eddy's research II (找规律)
- URAL 2070 Interesting Numbers (找规律)
- UVaLive 7269 Snake Carpet (找规律,模拟)
- 英语单词也有规律!!!
- 世间万物都是遵循某种类似的规律,谁先把握了这些规律,谁就最早成为了强者。
- LeetCode498之对角线遍历(寻找规律)
- LeetCode59之螺旋矩阵2(相关话题:找规律,思路代码简化)
- [记录]Ubuntu下,使用Shell,简单替换有规律的文件名称
- HDU 4919 打表找规律 java睑板 map 递归
- Codeforces 145A-Lucky Conversion(规律)