Just another WordPress.com site

Topics: http://uva.onlinejudge.org/external/102/10299.html
Reference: http://kos74185foracm.blogspot.com/2011/07/10299-relatives.html

The solution, if one is less than the number of n and n coprime, this number can not have the same prime factor with n.
Assume that n = 90 = 2 * 32 * 5, 90 quality factor have 2, 3, 5, the number of this question can not have a quality factor of these three.

We can use the exclusion principle obtained is less than n have the same qualitative factor and n the number of number:
(Number divisible by 2 + can be divisible by the number of + can be divisible by the number)     – (Can be 2,3 divisible by the number of + both 3,5 divisible by the number of + the number to be divisible by 2, 5)  + Can be 2,3,5 divisible by the number of

N = 90, for example, have a common factor and n the number of total:
(45 + 30 + 18) – (15 + 6 + 9) + 3 = 66 and

we are looking for the number of coprime with 90, 90 – 66 = 24.

We can simplify the above equation to derive a general formula:

Therefore less than n and coprime with n the number of number as follows:

Simple Discussion on Solution :

e.g. 9, We know 1, 2, 4, 5, 7, 8, Answer is 6.

And we found just 3 then (9%3) will true.
We got 9/3 = 3.
If you see the blog I linked to, he write that Answer = 9*(1-1/3), so 9*2/3 = 6.
And My code is 9*(1-1/3) => 9*(3/3-1/3) => 9/3*(3-1) => 3*(3-2).
so got that 3*(3-1) = 2.
1000000000 is the question require for.. N <= 1000000000
And we calculate that the prime number <= sqrt(1000000000) have 3401.
So we know that if has n that (n%prime[0...3401]) always false, that n is prime number.
if n >= prime[3401] and n is prime
then n%prime[0...3401]==0 not be true
So that n is not equal 1.
e.g. 2147483647 <= Just a example, not for this question
We got that 2147483647*(1-1/2147483647), so it's 2147483646.

#include <stdio.h>

1 int prime[3401] ={2},top=1;
2 void sieve();
3
4 int main()
5 {
6         sieve();
7         int n;
8         while(scanf("%d",&n)==1 && n)
9         {
10                 int soln = n;
11                 if(n == 1)
12                 {
13                         puts("0");
14                         continue;
15                 }
16                 for(int i=0;i<top && n >=prime[i];i++)
17                 {
18                         if(n%prime[i] == 0)
19                         {
20                                 while(n%prime[i] == 0)
21                                         n /= prime[i];
22
23                                 soln /= prime[i];
24                                 soln *= prime[i]-1;
25
26                         }
27                 }
28                 if(n != 1) soln/=n, soln*=(n-1);
29                 printf("%d\n",soln);
30         }
31 }
32 void sieve()
33 {
34         for(int i=3; i*i <= 1000000000 ; i+=2)
35         {
36                 int judge =1;
37                 for(int j=2;j*j <= i ;j++)
38                 {
39                         if(i%j == 0)
40                                 judge =0;
41                 }
42                 if(judge)
43                         prime[top++] = i;
44         }
45 }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: