Sort by

recency

|

6 Discussions

|

  • + 0 comments

    Another variation of the theme, at least I did it by myself ;-)
    Python3

    '''
    move is: a -> 2a -> 4a ... mod m , where m = (2n+1)
    Task: find minimal k so that [a * 2^k = a] holds.
    Answer then is:  2*n - k 
    a * (2^k - 1) = 0 mod m <=> a'*g * (2^k-1) = w * m'*g  
        where g=gcd(a,m), a'*g = a, m'*g = m, w =some number
        <=> a' * (2^k-1) = w * m'
    a' * (2^k-1) = 0 mod m' and gcd(a',m') = 1 = gcd(2,m')
    that is: 2^k = 1 mod m' => k|phi(m')
    '''
    
    import math
    from collections import Counter
    
    N = 10**9
    PRIMES = None
    
    def main():
        for _ in range(int(input())):
            n, a = map(int, input().split())
            print(solve(n, a))
    
    def solve(n, a):
        a, m = abs(a), 2*n+1
        g = math.gcd(a, m)
        a, m = a//g, m//g
        mf = factorize(m) 
        Kf = phi_from_fac(mf)
        for k in divs_from_fac(Kf):
            if pow(2, k, m) == 1:
                return 2*n - k
        else:
            raise RuntimeError('smells rotten')
    
    def factorize(n):
        global PRIMES
        if not PRIMES: init_primes()
        ret = Counter()
        nroot = math.isqrt(n)
        for p in PRIMES:
            if n == 1 or p > nroot: break
            e = 0
            while n%p == 0:
                n //= p
                e += 1
            if e > 0: ret[p] = e
        if n > 1:
            ret[n] = 1
        return ret
    
    def init_primes():
        global N, PRIMES
        cut = math.isqrt(N)
        sieve = [None] + [1] * cut
        for p in range(3, cut+1, 2):
            if sieve[p] == 0: continue
            for i in range(p*p, cut+1, 2*p):
                sieve[i] = 0
        ret = [2]
        for p in range(3, cut+1, 2):
            if sieve[p]: ret.append(p)
        PRIMES = ret
    
    def phi_from_fac(nfac):
        ret = +nfac
        for p in nfac.keys():
            ret[p] -= 1
            ret += factorize(p-1)
        return ret
    
    def divs_from_fac(nfac):
        ret = [1]
        for (p,e) in nfac.items():
            new = [a*p**i for a in ret for i in range(e+1)]
            ret = new
        return sorted(ret)
                
    main() 
    
  • + 1 comment

    Working Python3 code

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    from fractions import gcd
    
    # Sieve primes
    lim = 111111
    primes = [0] * 2 + [1] * (lim - 2)
    pc = 0
    for i in range(2, lim):
        if primes[i]:
            primes[pc] = i 
            pc += 1
            for j in range(i * i, lim, i):
                primes[j] = 0
    
    def prime_fac(n):
        ''' yields all prime-exponent pairs of the factorization of n '''
        if n == 1: 
            return
        for pi in range(pc):
            p = primes[pi]
            if p * p > n:
                p = n
            e = 0
            while n % p == 0:
                n //= p 
                e += 1
            if e:
                yield p, e
            if n == 1:
                break
    
    def phi(n):
        ''' Euler's totient of n '''
        for p, e in prime_fac(n):
            n -= n // p
        return n
    
    divs = [1] * lim
    
    def divisors(n):
        ''' yields all divisors of n '''
        yield 1, 1
        dc = 1
        for p, e in prime_fac(n):
            odc = dc
            for t in range(odc * e):
                old = divs[dc - odc]
                new = divs[dc] = old * p 
                dc += 1
                yield new, old
    
    z = int(input())
    assert 1 <= z <= 1000
    for cas in range(z):
        n, a = map(int, input().strip().split())
        assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
        m = 2 * n + 1
        m //= gcd(a, m)
        dp = {}
        for k, kold in sorted(divisors(phi(m))):
            dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
            if dp[k] == 1:
                print(2 * n - k)
                break
    
  • + 0 comments

    Observe that adding a "Room 0" doesn't change the results.

    => The task is to find the smallest n such that 2^n*A=A, mod (2N+1)

    => Divide all by gcd(A, 2N+1), then it becomes Euler's Theorem.

    => One way to find a candidate n is to use Euler's totient function.

    No. of rooms visited before returning to start will be n, or a factor of n.

  • + 1 comment
    n=int(input())
    k=[]
    l=[]
    f=0
    z=[]
    for i in range(n):
        a,b=input().split()
        for j in range(1,2*int(a)):
            if j<int(a):
                k.append(j)
            elif j==int(a):
                k.append(j)
                k.append(-j)
            elif j>int(a):
                x=j-2*int(a)
                k.append(x)
        if int(b)>0:
            l.append(int(b))
            f=k[int(b)+int(b)-1]
            while f in k and l.count(f)<=1:
                if f>0:
                    if f not in l:
                        l.append(f)
                    f=k[f+f-1]
                elif f<0:
                    if f not in l:
                        l.append(f)
                    f=k[k[f]+f]
                    l.append(f)
        l=list(dict.fromkeys(l))
        if int(b)<0:
            l.append(int(b))
            f=k[k[int(b)]+int(b)]
            while f in k and l.count(f)<=1:
                if f>0:
                    if f not in l:
                        l.append(f)
                    f=k[f+f-1]
                elif f<0:
                    if f not in l:
                        l.append(f)
                    f=k[k[f]+f]
                    l.append(f)
        l=list(dict.fromkeys(l))
        k.sort()
        l.sort()
        for s in k:
                if s not in l:
                    z.append(s)
        u=0
        for i in z:
            u+=1
        print(u)
    		
    		My test cases 0 and 1 ran successfully, but for the remaining test cases, it says terminated due to timeout. Please suggest edits to my code.
        k=[]
        l=[]
        f=0
        z=[]
    
  • + 1 comment

    Any hint on other patterns to be observed ? :
    1. f(N,A) == f(N,-A)
    2. When (2N+1) is prime, A is irrelevant.

     N : abs(A)
     1 :  0
     2 :  0  0
     3 :  3  3  3
     4 :  2  2  6  2
     5 :  0  0  0  0  0
     6 :  0  0  0  0  0  0
     7 : 10 10 10 10 12 10 10
     8 :  8  8  8  8  8  8  8  8
     9 :  0  0  0  0  0  0  0  0  0
    10 : 14 14 17 14 14 17 18 14 17 14
    11 : 11 11 11 11 11 11 11 11 11 11 11
    12 :  4  4  4  4 20  4  4  4  4 20  4  4
    13 :  8  8 20  8  8 20  8  8 24  8  8 20  8
    14 :  0  0  0  0  0  0  0  0  0  0  0  0  0  0
    15 : 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25
    16 : 22 22 22 22 22 22 22 22 22 22 30 22 22 22 22 22
    17 : 22 22 22 22 31 22 30 22 22 31 22 22 22 30 31 22 22
    18 :  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
    19 : 26 26 26 26 26 26 26 26 26 26 26 26 36 26 26 26 26 26 26
    20 : 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20