Relatives POJ - 2407(不打表的欧拉函数单求）

比眉伴天荒 2023-08-17 15:41 79阅读 0赞

# Relatives POJ - 2407 #

题目链接：[https://vjudge.net/problem/POJ-2407\#author=0][https_vjudge.net_problem_POJ-2407_author_0]

## 题目： ##

给定n是一个正整数，有多少正整数小于n是n的相对素数？ 如果没有整数x> 1，y> 0，z> 0使得a = xy且b = xz，则两个整数a和b是相对素数。  
输入  
     有几个测试用例。 对于每个测试用例，标准输入包含n <= 1,000,000,000的行。 在最后一种情况下，包含0的行。  
产量  
     对于每个测试用例，应该有单行输出来回答上面提出的问题。  
样本输入  
  
    7  
    12  
    0  
  
样本输出  
  
    6  
    4

**思路：一开始打表做发现不行，数据范围太大，会超内存，RE，只能单个求**

//
    // Created by hanyu on 2019/8/9.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int maxn=3e6+7;
    #define MAX 0x3f3f3f3f
    ll value(ll n)
    {
       ll result=n;
       for(int i=2;i*i<=n;i++)
       {
           if(n%i==0)
           {
               result=result/i*(i-1);
               while(n%i==0)
                   n/=i;
           }
       }
       if(n>1)
           result=result/n*(n-1);
       return result;
    }
    int main()
    {
        ll n;
        while(~scanf("%lld",&n)&&n)
        {
            printf("%lld\n",value(n));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11328908.html

[https_vjudge.net_problem_POJ-2407_author_0]: https://vjudge.net/problem/POJ-2407#author=0

发表评论取消回复

表情：

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

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

相关阅读

相关 poj3090（欧拉函数）

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

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

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

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

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

相关 Relatives POJ - 2407(不打表的欧拉函数单求）

Relatives POJ - 2407 题目链接：[https://vjudge.net/problem/POJ-2407\author=0][https_vjudge

比眉伴天荒/ 2023年08月17日 15:41/ 0 赞/ 80 阅读

相关 poj 2478 欧拉函数

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

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

相关欧拉函数

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

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

相关 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 赞/ 131 阅读

相关 POJ - 2407 - Relatives（欧拉函数 + 约数个数定理）

求出比n小，且与n互素数的个数；模板题，对于一个大于1正整数n可以分解质因数： ![这里写图片描述][a8ec8a13632762d0a5814266a7ec08fa50

青旅半醒/ 2022年06月08日 11:21/ 0 赞/ 150 阅读

相关欧拉函数

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

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

相关筛法求欧拉函数（poj2478

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

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

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

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

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