GitBook

这里写图片描述 这里写图片描述

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

其实只要做个减法就好了

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

#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