For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one . The first few integers in this class are . Denote as the -th smallest integer in this class. To make it even larger, we consider integers in the form of
. Now, given a prime number , how many pairs are there such that 1
The input contains multiple cases. The first line of the input contains a single integer , the number of cases.
For each case, the input consists of a single line, which contains 3 positive integers .
链接🔗
「NewCode 2019-3」 E. Big Integer
题解
化简等式
根据 定理 , 线性同余方程有解,当且仅当
当 时,显然无解,输出 即可
否则根据欧拉定理,
因此我们需要找到 的循环节 ,也就是最小正整数解
根据欧拉定理推论: 若互质,则满足 的最小正整数解 是 的约数。
因为,所以直接暴力枚举的约数,用快速幂进行验证是否正确即可
接下来我们统计有多少 满足 即可
根据算术基本定理,
考虑枚举,则 必须是 的倍数,则数量为
由于 ,所以我们仅需枚举到30即可,对于30以上的部分,值唯一
本题可能卡64位精度,建议在快速幂过程中,用快速乘代替基础乘运算
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long t,n,m,p;
const long long inf = 1e18;
long long phi(long long x)
{
long long ans = x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
ans = ans/i *(i-1);
while(x%i == 0) x/=i;
}
}
if(x>1) ans = ans/x * (x-1);
return ans;
}
long long pow(long long a,long long b, long long mod)
{
long long ans = 1ll;
while(b)
{
if(b&1) ans = mul(ans,a,mod);
a = a*a%mod;
b>>=1;
}
return ans;
}
long long find(long long x)
{
long long ans = x;
for(long long i = 1;i*i<=x;i++)
{
if(x%i==0)
{
if(pow(10,i,9*p) == 1) ans = min(ans,i);
if(pow(10,x/i,9*p) == 1) ans = min(ans,x/i);
}
}
return ans;
}
long long pri[50],c[50],tot;
void divide(long long n)
{
tot = 0;
for(int i=2;i*i<=n;i++)
{
if(n%i == 0)
{
pri[++tot] = i,c[tot]=0;
while(n%i==0) c[tot]++, n/=i;
}
}
if(n>1) pri[++tot] = n ,c[tot]=1;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld %lld",&p,&n,&m);
if(p%2==0||p%5==0)
{
printf("0\n");
continue;
}
long long d = find(phi(9*p));
//printf("%lld \n",phi(9*p));
divide(d);
long long ans = 0ll;
for(int j=1;j<=min(m,30ll);j++)
{
long long g =1ll;
for(int i=1;i<=tot;i++)
g *= pow(pri[i],((c[i]-1)/j+1),inf);
ans += n/g;
}
long long g = 1ll;
for(int i=1;i<=tot;i++) g*=pri[i];
if(m>30)
ans += (long long) (m-30) * (n/g);
printf("%lld\n",ans);
}
return 0;
}