Problem
Give you a modular equation ax=b (mod n). Count how many different x (0<=x<n) satisfying the equation.
Input
The input may contain several test cases.
Each test contains a line with three integers a, b and n, each integer is positive and no more than 10^9.
Input is terminated by EOF.
Output
For each test case, output a line containing the number of solutions.
Sample input
4 2 6
Sample output
2
#include <stdio.h>
long a,b,n;
int gcd(long a,long b)
{
if(a==0){
return b;
}
else
{
return gcd(b%a,a);
}
}
int main(){
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
long d=gcd(a,n);
if(b%d==0)
printf("%d\n",d);
else printf("0\n",d);
}
return 0;
}