Member Avatar for swissknife007
swissknife007 3 Junior Poster in Training 
There is a single ring road that runs over the circumference of this circle and connects all the boarding points. There are also N - 1 different shuttle agencies available in Bhiwani.
For every different boarding points A and B there is exactly one shuttle that connects these points and it belongs to Kth shuttle agency where K is the distance between A and B in clockwise direction, that is, there are exactly K - 1 boarding points between points A and B in clockwise direction. Denote this shuttle as (A, B). So if N = 4, first agency has shuttles (1,2), (2,3), (3,4), (4,1), second agency has shuttles (1,3), (2,4) and the shuttles of third agency are (1,4), (2,1), (3,2), (4,3). If the shuttle connects points A and B, it is possible to go from A to B as well as from B to A using this shuttle.
Chef is planning to make a contract with one of the agencies so that all of his employees are able to travel in shuttles of that agency for free. He therefore wants to choose such a shuttle agency so that people from any boarding point can reach his restaurant only using shuttles of the chosen agency possibly using some intermediate boarding points. Your task is to find how many such shuttle agencies are there.
Input

First line contains an integer T denoting number of test cases. After that T lines follow each containing a single integer N denoting number of shuttle boarding points in Bhiwani.
Output

For every test case, output the number of shuttle agencies our chef could choose.

I designed the code to solve this problem but I am not sure about the correct answers.
if someone could confirm me the answers for n=10000 is 4000 and n=1000 400 and n=15 8.Then I can be sure about it
thanks.

  • 1 Contributor
  • 0 Replies
  • 113 Views

Dani AI

Generated

— The three answers you listed are correct. For any N>1 the number of agencies that let everyone reach any boarding point using only that agency equals Euler's totient function phi(N). So phi(10000)=4000, phi(1000)=400, and phi(15)=8.

Reason: agency k links each vertex i with i+k (mod N). Repeatedly adding k visits exactly the residues in the additive subgroup generated by k mod N, which has size N/g where g = gcd(N,k). The edges therefore split the ring into g disjoint cycles, so the agency's graph is connected iff gcd(N,k)=1. Counting k in 1..N-1 with gcd(k,N)=1 gives phi(N). (Edge case: N=1 has no agencies, answer 0.)

Quick factor-based computation (sufficient for N up to ~1e12 with trial division; for much larger N use Pollard-Rho):

def phi_problem(n):
    if n == 1:
        return 0
    result = n
    p = 2
    while p*p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1 if p == 2 else 2
    if n > 1:
        result -= result // n
    return result

Practical tips: precompute primes and use the sieve-based totient array if many queries with max N up to ~1e7; otherwise factor each N and apply the formula result *= (1 - 1/p) for distinct prime factors p. Also note that k and N-k produce the same undirected edges but count as two distinct agencies when both are coprime to N.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.