분수의 순환절의 길이를 구하다

5394 단어

두 정수를 나누면 때때로 순환 소수가 발생하는데 그 순환 부분을 순환절이라고 부른다
예컨대, 11/13 = 0.846153153...그 순환절은 846153으로 모두 6위이다
 
아이디어:
시뮬레이션 나눗셈은 같은 여수를 찾기만 하면 순환절을 찾을 수 있다
 
코드는 다음과 같습니다.
 1 #include 
 2 #include <string.h>
 3 #include 
 4 #include <string>
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
12 #include 
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 vector<int> vt;
20 
21 int main()
22 {
23     int n,m;
24     scanf("%d %d",&n,&m);
25     int t=n;
26     int ans=0;
27     t=t%m;
28     while(1)
29     {
30         vt.push_back(t);//      
31         t*=10;
32         t=t%m;
33         if(t==0) break;    //     
34         else if(find(vt.begin(),vt.end(),t)!=vt.end())//
35         {
36             ans=vt.end()-find(vt.begin(),vt.end(),t);//       
37             break;
38         }
39     }
40     printf("%d
",ans); 41 return 0; 42 }

좋은 웹페이지 즐겨찾기