【杭电】[1787]GCD Again

问题描述

问题分析

欧拉函数的运用
只不过欧拉函数是求
1~N中与N互质的个数
这个是求不互质的个数

其实只要做个减法就好了

需要注意的是因为数据范围和内存限制
这一题不能用筛法做
直接用公式法好了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<string.h>
int f(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),n)
		printf("%lld\n",n-f(n)-1);
}

题目地址:【杭电】[1787]GCD Again