1.进制转换
1.1（10转其他进制）
string intToA(int n,int radix) //n是待转数字，radix是指定的进制
{
string ans="";
do{
int t=n%radix;
if(t>=0&&t<=9) ans+=t+'0';
else ans+=t-10+'a';
n/=radix;
}while(n!=0); //使用do{}while（）以防止输入为0的情况
reverse(ans.begin(),ans.end());
return ans;
}
1.2（其他进制转10）
int Atoi(string s,int radix) //s是给定的radix进制字符串
{
int ans=0;
for(int i=0;i<s.size();i++)
{
char t=s[i];
if(t>='0'&&t<='9') ans=ans*radix+t-'0';
else ans=ans*radix+t-'a'+10;
}
return ans;
}
2.分数取模
若存在整数a,p，满足gcd(a,p) == 1(即a，p互质)，则有a^(p-1)≡1(mod p)（就是a的p-1次幂对p取模与1恒等于1）//有费马小定理
对于整数a,p且gcd(a,p) == 1，则一定存在唯一一个b满足ab≡1(mod p) //乘法的逆元
即有 对于除法取模不成立，即(a/b)%p≠(a%p/b%p)%p。
求逆元的思路：(一般ACM的题目都是对 1e9 +7这种素数取模，所以gcd(a,p)==1)
ab=1(mod p) => b=1/a(mod p)。
根据费马小定理：b^(p-1)=1(mod p) => b^(p-2)=1/b(mod p)
可以看出来逆元1/b (mod p)=b^(p-2)
可以得出a/b对质数p取模就是 a*b^(p-2) mod p //结论，可以使用快速幂模板
ll qmi(int m, int k, int p)
{
ll res = 1 % p;
while (k)
{
if (k & 1) res = res * m % p;
m = m * m % p;
k >>= 1;
}
return res % p;
}
3.s中t字符串的数量
//dp[ s.size() ] [ t.size() ]
//dp[0] [j] = 0; //初始化
//dp[i] [0]= 1; (包含空串)
//dp[0] [0]= 1 （防止第一个条件覆盖
int tnum(string s, string t)
{
dp[0][0] = 1;
for(int i = 1; i <= s.size(); i ++)
{
dp[i][0] = 1;
for(int j = 1; j <= t.size(); j ++)
{
dp[i][j] = dp[i - 1][j];
if(s[i] == t[j]) dp[i][j] += dp[i - 1][j - 1];
}
}
return dp[s.size()][t.size()];
}
//一维数组
int tnumn(string s, string t)
{
for(int i = 0; i < s.size(); i ++)
{
for(int j = t.size() - 1; j >= 1; j --)
{
if(s[i] == str[j])
{
ans[j] += ans[j - 1];
}
}
if(s[i] == str[0])
{
ans[0] += 1;
}
}
return ans[2];
}
4.试除法求所有约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
5. 约数个数和约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
6.拓展欧几里得
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
7.递推求组合数(杨辉三角)
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
8.快读快写
__int128 read(){
__int128 x=0;bool f=0;char c=getchar();
while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline void write(__int128 x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
9. 快速幂
ll ksm(ll a,ll b,ll mod)
{
ll res = 1;
while(b){
if(b & 1) res = (ll)res*a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
10.如何找到p/q的循环节？
考虑1/q
1.如果q中仅含有2或5，那么该小数是有限循环小数
2.如果不含2或5，10与q互素，根据欧拉定理，10^Φ(q)≡1(%q)，其中Φ(q)便是循环节，但不一定是最小的，因为最小的循环节重复k遍仍是循环节，所以通过遍历Φ(q)的因子找到最小的循环节即可。
3.如果出了2和5还有其他的，先找出2和5的个数分别为a与b，循环节前面一段的长度就是max(a,b)，剩下的10与q除掉2a,5b互素，找到最小循环节即可。
#include<bits/stdc++.h>
//大整数取模要用__int128
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define endl "\n"
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
const int N=1e5+10;
const int INF=0x3f3f3f3f;
__int128 gcd(__int128 a, __int128 b) { return b ? gcd(b, a % b) : a;}
__int128 read(){
__int128 x=0;bool f=0;char c=getchar();
while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline void write(__int128 x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
__int128 phi(__int128 x)
{
__int128 res = x;
for(__int128 i = 2; i <= x / i; i ++)
if(x % i == 0)
{
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
if(x > 1) res = res / x * (x - 1);
return res;
}
__int128 ksm(__int128 a,__int128 b,__int128 mod)
{
__int128 res = 1;
while(b){
if(b & 1) res = (__int128)res*a % mod;
a = (__int128)a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
__int128 p, q;
p = read(), q = read();
__int128 d = gcd(p, q);
q /= d;
__int128 cn2 = 0, cn5 = 0;
while(q % 2 == 0) q /= 2, cn2 ++;
while(q % 5 == 0) q /= 5, cn5 ++;
//write(q);
//cout << endl;
if(q == 1)
{
cout << "-1" << endl;
return 0;
}
__int128 t = phi(q);
__int128 res = 1e18;
for(__int128 i = 1; i <= t / i; i ++)
{
if(t % i == 0)
{
__int128 x1 = i;
__int128 x2 = t / i;
if(ksm(10, x1, q) == 1) res = min(res, x1);
if(ksm(10, x2, q) == 1) res = min(res, x2);
}
}
write(max(cn2, cn5));
cout << ' ';
write(res);
return 0;
}