Submission #73508932

---

Source Code Expand

import sys
from collections import deque, defaultdict, Counter
from heapq import heappop, heappush, heapify
from itertools import product, combinations, accumulate, permutations, groupby
from math import sqrt, isqrt, comb, gcd

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

DIR4 = [(1,0),(-1,0),(0,1),(0,-1)]
DIR8 = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]

INF = 10**18
YES,NO = "Yes", "No"

def ni(): return int(input())
def nm(): return map(int,input().split())
def nl(): return list(nm())

def si(): return input().strip()
def sm(): return si().split()
def sl(): return list(si())


def main():
    m,a,b = nm()
    # a = 1, b = 1
    # x = 1, y = 1
    # [1, 1, 2, 3, 5, 8, 13, 21, ]
    ans = 0
    for x in range(1,m):
        for y in range(1,m):
            l = [x, y]
            for i in range(2,(10**7)//(m**2)):
                l.append((a*l[i-1] + b*l[i-2])%m)
                if (l[i]) % m == 0:
                    break
            else:
                # print(x,y)
                ans += 1
                # print(l)



    print(ans)

if __name__ == '__main__':
    main()

Submission Info

Judge Result