Question

C++的一道取模有关的题目

我从1开始一个一个检验，毫无疑问超时了，有多组测试
(a * x + b) % n = 0，给定正整数a,b,n，输出最小的正整数x，使之成立，若不存在输出-1，a,b,n不超过2000000000
给个算法啊，我今天下午上网看了很多模运算性质公式还是不会
Description

Given an equation (a * x + b) % n = 0, where a,b,n are positive integers, please find out the least positive integer x make that equation holds.

Input

There are several test cases, one line for each case. For each line, there are three positive integers, all of which are no more than 2000000000. Input numbers have no leading zeros. There will be no more than 1000 test cases.
Input is ended with three 0.

Output

Output each result in one line. Output number must not have any leading zeros. If there is no positive integer makes the equation holds, then output -1.

最后试了还是不行，超时，算了，我以后学了数论再来看看

Answer 1

int main()
{
int a,b,n;
int j=0;
printf("please input the value of a,b,n:");
scanf("%d,%d,%d",&a,&b,&n);
if((n-b)%a!=0&&a!=b!=c)
{
printf("%d",-1);
return 0;
}
for(int i=1;;i++)
{
while(a*j+b!=i*n)
{
j++;
}

if(a*j+b==i*n)
break;
}

printf("%d\n",j);
}
看看行不。。

追问

明显不行...

追答

你测试了？

Answer 2

没有想到什么好办法，但是循环n比较慢，循环它们除的结果快很多，代码参考一下
int getMinX(const unsigned int a, const unsigned int b, const unsigned int n)
{
int minX = -1;
int i = 0;
int dis = 0;
set<unsigned int> remainders;
while (++i)
{
dis = (i * n - b) % a;
if (dis == 0)
{
minX = (i * n - b) / a;
break;
}
else
{
if (remainders.find(dis) == remainders.end())
{
remainders.insert(dis);
}
else
{
break;
}
}
}

return minX;
}

追问

当a,b,n依次为 43 56 13时，应该输出12，你的代码直接输出-1了，我把其中
minX = (i * n - b) / a;
break;
改为
minX = (i * n - b) / a;
if(minX>0) break;
答案就没错，但是超时了

追答

重新优化了算法，现在在试试嘛。
int getMinX(const unsigned int a, const unsigned int b, const unsigned int n)
{
int remainder = (n - b % n) % n;
int i = 1;
int dis = 0;
int step = 0;

int firstRemainder = dis = a % n;
if (firstRemainder == remainder) return i;

do
{
if (a > n)
{
++i;
}
else
{
if (dis < remainder)
{
step = remainder - dis;
}
else
{
step = remainder + n - dis;
}

if (step % a) step = step / a + 1;
else step = step / a;

i += step;
}

dis = (a * i) % n;
if (dis == remainder) return i;
} while (dis != firstRemainder);

return -1;
}