Send a Table UVA - 10820——欧拉函数初级应用

超、凢脫俗 2022-06-15 08:53 134阅读 0赞

Think:  
1分析+欧拉函数  
2紫书分析:输入一个n值，判断有多少个二元组(x, y)满足1 <= x, y <= n, 且x, y互素, 可以发现,除了(1, 1)之外，其他的x, y都不相等，设满足x < y 的二元组有f(n)个，则ans = 2\*f(n) + 1;由欧拉函数的定义可以得到f(n) = phi\[2\] + phi\[3\] + … + phi\[n\];  
3欧拉函数:  
phi\[n\]:满足

/*
    欧拉函数:计算小于n且与n互素的整数个数
    */
    #include <cstdio>
    #include <cstring>
    
    void phi_table(int n, int *phi){
       ///计算1~n中所有数的欧拉phi函数值
        for(int i = 0; i <= n; i++){
            phi[i] = 0;
        }
        phi[1] = 1;
        for(int i = 2; i <= n; i++){
            if(!phi[i]){
                for(int j = i; j <= n; j += i){
                    if(!phi[j])
                        phi[j] = j;
                    phi[j] = phi[j] / i * (i-1);
                }
            }
        }
    }
    
    int main(){
        int n, ans, phi[50004];
        phi_table(50000, phi);
        while(scanf("%d", &n) && n){
            ans = 0;
            for(int i = 2; i <= n; i++){
                ans += phi[i];
            }
            printf("%d\n", 2*ans + 1);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关欧拉函数

欧拉函数 * 前言 * 求单个欧拉函数值 * 线性求欧拉函数前言在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目在...

曾经终败给现在/ 2024年04月18日 11:45/ 0 赞/ 86 阅读

相关欧拉函数 AcWing 873. 欧拉函数

欧拉函数 AcWing 873. 欧拉函数原题链接 [AcWing 873. 欧拉函数][AcWing 873.] 算法标签数学知识欧拉函数思路

绝地灬酷狼/ 2023年09月28日 11:38/ 0 赞/ 130 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

待我称王封你为后i/ 2022年07月29日 08:47/ 0 赞/ 239 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

向右看齐/ 2022年07月19日 01:23/ 0 赞/ 215 阅读

相关 Send a Table UVA - 10820——欧拉函数初级应用

Think: 1分析+欧拉函数 2紫书分析:输入一个n值，判断有多少个二元组(x, y)满足1 <= x, y <= n, 且x, y互素, 可以发现,除了(1, 1)

超、凢脫俗/ 2022年06月15日 08:53/ 0 赞/ 135 阅读

相关欧拉函数

欧拉函数在数论中指的是，对于正整数N,小于或等于N (\[1,N\]),且与N互质的正整数(包括1)的个数，记作φ(n)。以下是欧拉函数的模板 1，直接求φ(n

短命女/ 2022年06月12日 02:58/ 0 赞/ 220 阅读

相关【欧拉函数】

1.1欧拉函数定义首先，需要理解一下什么是欧拉函数，欧拉函数phi(n)的定义为小于等于n且与n互素的整数个数。那么什么是互素呢？互素是指对于两个数a和b，a和b的最大公

雨点打透心脏的1/2处/ 2022年06月09日 00:40/ 0 赞/ 286 阅读

相关欧拉函数模板

欧拉函数模板欧拉函数是用来求给定一个属n，小于等于n的与n互质的数的数目代码： include <bits/stdc++.h> using names

向右看齐/ 2022年05月31日 09:44/ 0 赞/ 223 阅读

相关欧拉函数

定义在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。通式 ![70][

落日映苍穹つ/ 2022年05月16日 07:58/ 0 赞/ 298 阅读

相关欧拉函数|(扩展)欧拉定理|欧拉反演

[也许更好的阅读体验][Link 1] 欧拉函数欧拉函数是小于 n的数中与n 互质的数的数目符号\\(\\varphi(x)\\)

忘是亡心i/ 2021年11月09日 20:06/ 0 赞/ 448 阅读