How do I optimize a piece of code to execute under 2 seconds

For a coding practice challenge I wrote this python code, but is giving 6 seconds of execution time but I want it to execute under 2 seconds. How should I modify this code? Future tips also welcomed.

times = int(raw_input())

for i in range (times):
    count = 0
    z =  raw_input().split()
    a,d = int(z[0]),int(z[1])
    p= int(raw_input())
    while a%p != 0:
        a= a+d
        count = count+1
    print count

Brief of the problem statement:

Input format: The first line contains a number, tc, denoting the number of test cases. The second line contains two integers, a and d - a depicts the first term in the AP, d depicts the common difference. The last line contains the prime number.

Output format: You have to print the FIRST index (0-based) of the multiple of the given prime number in the given AP. If no such element exists in this infinite AP, then print -1.

Constraints:

0 <= a, d, <= 10^18
1 <= p <= 10^9

Sample Input:

1
4 9
11

Sample Output:

2

Explanation: the AP would be: 4, 4+9=13, 13+9=22, 22+9=31 - and the prime number is 11, so the index is [2].

Answers


You forgot to change p%a to a%p, which was pointed out the last time you posted this question. You also forgot to clarify that it takes six seconds with the real data, not this test data.

The problem is that you're using an inefficient, brute-force algorithm. Try the extended Euclidean algorithm.


Need Your Help

c# form application label does not update

c# multithreading label rfid

Hi everyone this is my first question to stackoverflow and sorry for my English. I searched for a week and couldn't find the solution. I am working on a project which uses RFID antenna and tags . A

Android pull to refresh with ScrollView control

android android-layout android-widget pull-to-refresh

I am using a ScrollView to display a list of items that are inflated on runtime. Like a feed of updates for the user.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.