SGU

SGU"/>

SGU

题意：

求 a / b 的小数点后的循环节的开始点和循环节长度

至于整数，循环节长度为0，开始位置就是整除完了的后一位

思路：

直接模拟，出现重复的余数，说明出现了循环节，如果被整除了的话直接输出

本来看错数据大小了，用的 map 记录余数的位置，748ms 卡过，后来发现只有1e6 的数据，用数组记录就好了；

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
#define kuaidian ios::sync_with_stdio(0);using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 7, maxd = 670000 + 7;
const ll mod = 1e9 + 7;
const int INF = 0x7f7f7f7f;int x, y;
int vis[maxn] = {0};void solve() {int cnt = 1, a, b;x %= y;while(1) {if(x % y == 0) {printf("%d 0\n", cnt-1);return;}else if(x < y) {int t = x % y;if(vis[t] > 0) {a = vis[t];b = cnt - vis[t];printf("%d %d\n", a-1, b);return;}else {vis[t] = cnt++;}x *= 10;}else {x %= y;}}
}int main() {kuaidian;cin >> x >> y;solve();return 0 ;
}