【bzoj2190】[SDOI2008]仪仗队 欧拉函数
函数 欧拉
2023-09-11 14:22:40 时间
题目描述
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在,C君希望你告诉他队伍整齐时能看到的学生人数。
输入
共一个数N。
输出
共一个数,即C君应看到的学生人数。
样例输入
4
样例输出
9
题解
欧拉函数
将左下角的点的坐标视为(0,0),则如果一个除(0,1)和(1,0)以外点能够被看见,它的横纵坐标必定互质。
那么可以盖住左上半部分和对角线,那么每个横坐标i对应的能看到的点的个数就是φ(i)。
然后快筛欧拉函数即可。
别忘了还有(1,1)这个点,所以答案为2*∑φ(i)+1(1≤i<n)=2*∑φ(i)+3(2≤i<n)。
#include <cstdio> #include <algorithm> using namespace std; int f[40010] , sta[40010] , tot; bool p[40010]; int main() { int n , i , j , ans = 0; scanf("%d" , &n); for(i = 2 ; i < n ; i ++ ) { if(!p[i]) sta[++tot] = i , f[i] = i - 1; for(j = 1 ; j <= tot && i * sta[j] <= n ; j ++ ) { p[i * sta[j]] = 1; if(i % sta[j] == 0) { f[i * sta[j]] = f[i] * sta[j]; break; } else f[i * sta[j]] = f[i] * (sta[j] - 1); } ans += f[i]; } printf("%d\n" , ans * 2 + 3); return 0; }
相关文章
- SQL NULL 函数
- UVA 11426 GCD - Extreme (II) (数论|欧拉函数)
- Matlab中writecell函数的使用
- php 函数参数中三个点带变量名 (function add(.....$args))及相关函数应用示例
- MySQL 中 find_in_set() 函数的使用
- UVA 10837 - A Research Problem(欧拉函数)
- 【SPOJ419】Transposing is Fun Pólya定理+欧拉函数
- 【POJ2154】Color Pólya定理+欧拉函数
- 【BZOJ3518】点组计数 欧拉函数
- 【BZOJ2005】[Noi2010]能量采集 欧拉函数
- Selenium常用函数总结
- UVa 11440 Help Tomisu (数论欧拉函数)
- 《Swift 权威指南》——第6章,第6.2节返回多值的函数
- [转]MySQL常用Json函数和MySQL常用字符串函数
- mysql树型结构查询父类函数,mysql递归查询父类函数
- Vue2.0 —生命周期和钩子函数
- 【POJ 2480】Longge's problem(欧拉函数)
- mod_timer函数及其他定时器函数
- (4.34)sql server窗口函数
- 【Java实验】函数与日期类
- JavaScript函数注意点
- 【bzoj3560】DZY Loves Math V 欧拉函数
- 【bzoj2401】陶陶的难题I “高精度”+欧拉函数+线性筛
- 【bzoj2705】[SDOI2012]Longge的问题 欧拉函数