2013
11-11

# Relatives

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.

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.

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

7
12
0


6
4




import java.util.Scanner;
import java.util.Arrays;
public class Main {
// 求从1到n-1与n互质的数的个数,代码如下
static int eular(int n)
{
int ret = 1,i;
for (i = 2;i * i <= n;i++)
if (n % i == 0)
{
n /= i;
ret *= (i - 1);
while (n % i == 0)
{
n /= i;
ret *= i;
}
}
if (n > 1)
ret *= (n - 1);
return ret;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

while(sc.hasNext()){
int n=sc.nextInt();
if(n==0) break;
System.out.println(eular(n));
}
}
}

//* @author  [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.util.HashSet;
import java.util.Scanner;
import java.util.Vector;

public class Main {

public static Vector< Double> fact(double n){
HashSet< Double> set=new HashSet< Double>();
while(n%2==0){
n/=2;
}
double k=3;
while(k<=(Math.sqrt(n+0.0)+1)){
if(n%k==0){
n/=k;
}
else k+=2;
}
return new Vector< Double>(set);
}

public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=0;
double val=0;
Vector< Double> set;
while((n=scan.nextInt())!=0){
val=n;
set=fact(n);
for(int i=0;i< set.size();i++){
val*=1.0-1.0/set.get(i);
}
System.out.println((int)val);
}
}
}

1. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环