|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Accepted | ace | 1259. How to Become Star? | 12 Feb 2014 02:34 | 3 | #include<iostream>
using namespace std;
int GCD( int a, int b )
{
a = abs( a );
b = abs( b );
while ( b )
{
int tmp = a % b;
a = b;
b = tmp;
}
return ( a );
}
int main()
{ int s=0,n,i;
cin>>n;
for(i=1;i<=n/2;i++)
if(GCD(n,i)%n==1)
s++;
cout<<s;
system("pause");
return 0;
} can't believe somebody used system("pause"); Should'nt this code be deleted by the admins?
Edited by author 12.02.2014 02:34 | | interesting | Hanzbrow (TNU) KCC | 1259. How to Become Star? | 27 Jun 2011 14:49 | 3 | Hi!
I think I have a solution.
it lays on geometrical thoughts.
please give me answers on tests from 10-...
any help, please.
#include<iostream>
using namespace std;
int main() {
int n;
cin>>n;
cout<<n/4+1;
return 0;
}
Edited by author 28.07.2009 16:43 N = 18
answer is 3
in your solution it`s 5... Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com | | Why WA6? | Slava Muravjev | 1259. How to Become Star? | 3 Jan 2011 17:42 | 1 | Why WA6? Slava Muravjev 3 Jan 2011 17:42
Edited by author 03.01.2011 18:06 | | Solution | Tigran92[RAU_902] | 1259. How to Become Star? | 24 Nov 2010 23:42 | 1 | Solution Tigran92[RAU_902] 24 Nov 2010 23:42 Just calculate number of i-s that, gcd(n,i)==1,where 1<=i<=(n>>1)
Edited by author 24.11.2010 23:43
Edited by author 24.11.2010 23:43 | | How to solve this problem?? | Saturn | 1259. How to Become Star? | 4 Jul 2010 20:15 | 7 | var
m,i,n,n1:longint;
function nod(a,b:longint):longint;
{...}
end;
begin
readln(n);
n1:=(n-1) div 2;
m:=0;
for i:=1 to n1 do
if nod(i,n)=1 then inc(m);
writeln(m);
end. why? The Big Bad Wolf (Cristina Stancu-Mara) 18 Feb 2005 17:11 i did the problem like u suggested:) and i got accepted but i dont really understand why is it like that..can u please explain me?
Edited by author 18.02.2005 17:12
Edited by author 18.02.2005 17:12 Re: why? Michael Rybak (accepted@ukr.net) 3 Feb 2006 19:29 //
below I use divisibility by a real (not integer) number - hope that doesn't cause any confusions
//
Let us denote beta = Pi - alpha (from problem statement)
You can easily prove that the process described in the problem statement means that we simply fix the initial point on a circle, and then jump around with angle beta.
So now for given N you need to find the number of solutions for the following equalty:
N * beta mod 2Pi = 0, such that N is minimal
Obviously, beta must be p / N * Pi, where p is integer (elseway N * beta can't be divisible by 2Pi).
But beta = Pi - alpha and 0 < alpha < Pi, so 0 < beta < Pi;
this means that 0 <= p < N. On the other hand, p must be even - if it's not, N * beta = N * p / N * Pi = p * Pi will not be divisible by 2Pi. So p = 2 * i.
So we have the following candidates for beta: 2 * i / N * Pi, where 0 <= i < N div 2 (because p < N).
The last thing to take care of is that there's no such K < N that K * beta is divisible by 2Pi:
K * 2 * i / N * Pi (not divisble by) 2Pi.
This means that K * i must not be divisible by N for any K < N; which means that i and N must be coprimes.
So the answer is number of coprimes of N that are smaller that N / 2. If A and N are coprimes, then (N-A) and N are coprimes too, so the answer is (number of coprimes of N that are smaller that N) / 2.
To calculate this number we can use Euler's formula instead of a bruteforce solution:
if N = a1^p1 * a2^p2 * .. * ak^pk, where all ai are different and all ai are primes, then number of coprimes smaller than N is
E(N) = (a1 - 1) * .. * (ak - 1) * a1 ^ (p1 - 1) * .. * ak ^ (pk - 1)
so the answer is E(N) / 2
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n / 2; i++)
{
if (gcd(i, n) == 1)
ans++;
} | | I have in passing received values an alpha | Burmistrov Ivan | 1259. How to Become Star? | 1 Dec 2005 00:01 | 1 | I got AC time 0.14. This is not big decision, but I have in passing received values an alpha, and absolutely exact (in a format pi*k/n). | | How to slove 1259? Maths? | tbtbtb91 | 1259. How to Become Star? | 7 Apr 2004 08:44 | 5 | You should just draw a little. something with the primes numbers... Thank you! I have got AC.... |
|
|
|
