♥BZOJ 2190: [SDOI2008]仪仗队【欧拉函数】

淩亂°似流年 2022-07-29 08:48 136阅读 0赞

## 2190: \[SDOI2008\]仪仗队 ##

Time Limit: 10 Sec Memory Limit: 259 MB  
Submit: 2298 Solved: 1438  
\[[Submit][]\]\[[Status][]\]\[[Discuss][]\]

## Description ##

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \* N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 　　 ![2190.jpg][] 　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

## Input ##

共一个数N。

## Output ##

共一个数，即C君应看到的学生人数。

## Sample Input ##

4

## Sample Output ##

9

## HINT ##

【数据规模和约定】 　　对于 100% 的数据，1 ≤ N ≤ 40000

解题思路:

沿对角线分成两半，我们可以看到下三角中出最后一行之外，每一列都是欧拉函数。

#include<stdio.h>
    int euler(int n){     
         int res=n,a=n;    
         for(int i=2;i*i<=a;i++){    
             if(a%i==0){    
                 res=res/i*(i-1);    
                 while(a%i==0) a/=i;    
             }    
         }    
         if(a>1) res=res/a*(a-1);    
         return res;    
    }    
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		if(n==1)
    		{
    			printf("1\n");
    			continue;
    		}
    		int ans=0;
    		for(int i=1;i<=n-1;i++)
    		{
    			ans+=euler(i);
    		}
    		printf("%d\n",2*ans+1);
    	}
    	return 0;
    }

[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=2190
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=2190
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=2190
[2190.jpg]: http://www.lydsy.com/JudgeOnline/images/2190.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉函数 AcWing 873. 欧拉函数

欧拉函数 AcWing 873. 欧拉函数原题链接 [AcWing 873. 欧拉函数][AcWing 873.] 算法标签数学知识欧拉函数思路

绝地灬酷狼/ 2023年09月28日 11:38/ 0 赞/ 130 阅读

相关【日常学习】【欧拉函数】codevs2296 仪仗队题解

转载请注明出处 \[ametake版权所有\][http://blog.csdn.net/ametake][http_blog.csdn.net_ametake]欢迎

绝地灬酷狼/ 2022年08月05日 04:18/ 0 赞/ 103 阅读

相关 ♥BZOJ 2190: [SDOI2008]仪仗队【欧拉函数】

2190: \[SDOI2008\]仪仗队 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 2298 Solved:

淩亂°似流年/ 2022年07月29日 08:48/ 0 赞/ 137 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

待我称王封你为后i/ 2022年07月29日 08:47/ 0 赞/ 239 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

向右看齐/ 2022年07月19日 01:23/ 0 赞/ 215 阅读

相关欧拉函数

欧拉函数在数论中指的是，对于正整数N,小于或等于N (\[1,N\]),且与N互质的正整数(包括1)的个数，记作φ(n)。以下是欧拉函数的模板 1，直接求φ(n

短命女/ 2022年06月12日 02:58/ 0 赞/ 220 阅读

相关【欧拉函数】

1.1欧拉函数定义首先，需要理解一下什么是欧拉函数，欧拉函数phi(n)的定义为小于等于n且与n互素的整数个数。那么什么是互素呢？互素是指对于两个数a和b，a和b的最大公

雨点打透心脏的1/2处/ 2022年06月09日 00:40/ 0 赞/ 286 阅读

相关 HYSBZ-2190(欧拉函数）&&hdu-2814(容斥原理)

问题描述：作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \ N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人

青旅半醒/ 2022年06月09日 00:17/ 0 赞/ 162 阅读

相关洛谷P2158 [SDOI2008]仪仗队

题目描述作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \ N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生

傷城~/ 2022年05月25日 01:28/ 0 赞/ 144 阅读

相关欧拉函数

定义在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。通式 ![70][

落日映苍穹つ/ 2022年05月16日 07:58/ 0 赞/ 298 阅读