B. Position in Fraction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You have a fraction . You need to find the first occurrence of digit c into decimal notation of the fraction after decimal point.
Input
The first contains three single positive integers a, b, c (1 ≤ a < b ≤ 105, 0 ≤ c ≤ 9).
Output
Print position of the first occurrence of digit c into the fraction. Positions are numbered from 1 after decimal point. It there is no such position, print -1.
Examples
input
1 2 0
output
2
input
2 3 7
output
-1
Note
The fraction in the first example has the following decimal notation: . The first zero stands on second position.
The fraction in the second example has the following decimal notation: . There is no digit 7 in decimal notation of the fraction.
【题意】：给定分子m 分母n和一个数c，找出c在m/n的循环节第几个位置出现，没出现过输出-1。
【分析】：模拟实现循环节，记录出现过的下标。
【代码】：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+;
int i,pos=-,c;
int main()
{
int n,m,i;
scanf("%d%d%d",&m,&n,&c);
i=;
int cnt=;
int fz=m,fm=n;
while()
{
i++;
fz=fz*;
//printf("%d",fz/fm);
if(fz/fm==c)
{
pos=i;
break;
}
fz=fz%fm;
if(i>=) break; //限制循环节长度
}
printf("%d\n",pos);
return ;
}
