百万小小兵 (HGOI 2019.2.17 T1)

2019-02-17 13:55:47


题目大意

求1~n与n不互质的数的个数

数据范围

n<=10000000

解法

很简单,很无脑

求一下欧拉函数,减一下就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int Ola(int x)
{
    int res=x,k=x;
    for(int i=2;i*i<=x;i++)
        if(k%i==0)
        {
            res=res/i*(i-1);
            while(k%i==0) k/=i;
        }
    if(k>1) res=res/k*(k-1);
    return res;
}
int main()
{
    scanf("%d",&n);
    printf("%d",n-Ola(n));
    return 0;
}