筛法求欧拉函数（poj2478

谁践踏了优雅 2021-10-30 01:38 344阅读 0赞

求1～n的欧拉函数的值

#include <iostream>
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #define inf 2147483647
    #define N 1000010
    #define p(a) putchar(a)
    #define For(i,a,b) for(long long i=a;i<=b;++i)
    
    using namespace std;
    long long n;
    long long a[N];
    void in(long long &x){
        long long y=1;char c=getchar();x=0;
        while(c<'0'||c>'9'){
        if(c=='-')y=-1;c=getchar();}
        while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();}
        x*=y;
    }
    void o(long long x){
        if(x<0){p('-');x=-x;}
        if(x>9)o(x/10);
        p(x%10+'0');
    }
    
    int main(){
        a[1]=1;
        For(i,2,1e6)
            if(!a[i])
                for(long long j=i;j<=1e6;j+=i){
                    if(!a[j]) a[j]=j;
                    a[j]=a[j]/i*(i-1);
                }   
        For(i,1,1e6)
            a[i]+=a[i-1];
        while(cin>>n&&n){
            o(a[n]-1);p('\n');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/war1111/p/11301031.html

发表评论取消回复

表情：

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

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

相关阅读

相关 poj2478 （欧拉函数）

Farey Sequence <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

深藏阁楼爱情的钟/ 2024年02月17日 21:36/ 0 赞/ 42 阅读

相关关于欧拉筛法和普通筛法

为的是让一个合数只让最小的一个素数筛去 prime\[\]数组中的素数是递增的,当i能整除prime\[j\]，那么i\prime\[j+1\]这个合数肯定被pri

「爱情、让人受尽委屈。」/ 2024年02月17日 21:36/ 0 赞/ 97 阅读

相关欧拉函数 AcWing 874. 筛法求欧拉函数

欧拉函数 AcWing 874. 筛法求欧拉函数原题链接 [AcWing 874. 筛法求欧拉函数][AcWing 874.] 算法标签数学知识欧拉函

超、凢脫俗/ 2023年09月28日 11:41/ 0 赞/ 9 阅读

相关 Farey Sequence POJ - 2478 (欧拉函数前缀和）

Farey Sequence POJ - 2478 题目链接：[https://vjudge.net/problem/POJ-2478][https_vjudge.net

ゞ浴缸里的玫瑰/ 2023年08月17日 15:40/ 0 赞/ 110 阅读

相关欧拉线性筛法（素数模板）

什么是素数？ ans：素数也又称质数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数。最小的质数是 2，它也是唯一的偶数质数。最前面的质

╰半橙微兮°/ 2023年07月01日 15:00/ 0 赞/ 6 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 161 阅读

相关 POJ 2478-Farey Sequence（欧拉函数）

Farey Sequence <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

亦凉/ 2022年08月21日 01:25/ 0 赞/ 20 阅读

相关 poj 2478 欧拉函数

Farey Sequence <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

红太狼/ 2022年08月10日 09:48/ 0 赞/ 62 阅读

相关筛法求欧拉函数（poj2478

求1～n的欧拉函数的值 include <iostream> include <cstdio> include <queue> include

谁践踏了优雅/ 2021年10月30日 01:38/ 0 赞/ 345 阅读

相关数论 - 欧拉函数【普通求法 + 筛法求欧拉函数】

欧拉函数 1.定义对于正整数n,欧拉函数是小于或等于n的正整数中(即1-n中)与n互质的数的数目，记作φ(n) 其中φ(1)=1。 2求n的

向右看齐/ 2021年07月24日 23:53/ 0 赞/ 459 阅读