POJ 2407-Relatives-欧拉函数

墨蓝 2022-08-21 01:25 23阅读 0赞

Relatives

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;12903</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6379</td> 
  </tr> 
 </tbody> 
</table>

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7
    12
    0

Sample Output

6
    4

Source

[Waterloo local 2002.07.01][]

题意：

给定一个数n，求所有小于等于n的正整数中，有多少个是与n互质的。

知识点：

欧拉函数，直接套模板。

#include<iostream>
    using namespace std;
    
    int oula(int n)//欧拉函数的函数模板
    {
        int i,ans=n;
        for(i=2;i*i<=n;++i)
            if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
        if(n>1)
            ans-=ans/n;
        return ans;
    }
    
    int main()
    {
    	int n;
    	while(cin>>n&&n)
            cout<<oula(n)<<endl;
    	return 0;
    }

[Waterloo local 2002.07.01]: http://poj.org/searchproblem?field=source&key=Waterloo+local+2002.07.01

发表评论取消回复

表情：

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

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

相关阅读

相关 poj2478 （欧拉函数）

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

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

相关 poj3090（欧拉函数）

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

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

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

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

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

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

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

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

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

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

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

相关 POJ 2407-Relatives-欧拉函数

Relatives <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

墨蓝/ 2022年08月21日 01:25/ 0 赞/ 24 阅读

相关 poj 2478 欧拉函数

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

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

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

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

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

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

相关筛法求欧拉函数（poj2478

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

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