筛法求欧拉函数（poj2478

谁践踏了优雅 2021-10-30 01:38 287阅读 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 条评论，287人围观）

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

相关阅读

相关欧拉筛&&埃氏筛

数论——欧拉筛、埃氏筛 `记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~` -------------------- 文章目录数论——欧

向右看齐/ 2024年03月30日 12:54/ 0 赞/ 34 阅读

相关 poj3090（欧拉函数）

Visible Lattice Points <table> <tbody> <tr> <td><strong>Time Limit:</strong>&n

末蓝、/ 2024年02月17日 21:36/ 0 赞/ 34 阅读

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

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

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

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

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

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

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

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

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

相关 poj 2478 欧拉函数

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

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

相关 poj-1284(欧拉函数+原根)

问题描叙: We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and o

落日映苍穹つ/ 2022年06月09日 00:27/ 0 赞/ 132 阅读

相关【二次爆炸记·第二弹】（欧拉筛法求约数和）Savrsen

文章目录题目题目描述输入格式输出格式样例样例输入1 样例

分手后的思念是犯贱/ 2021年11月24日 00:06/ 0 赞/ 235 阅读

相关筛法求欧拉函数（poj2478

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

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

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

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

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