题意
定义(A(n)) 为 n个1表示的十进制数，例如(A(3) = 111)
然后对于(1 le i le n,1le j le m) 问有多少的 (pairs(i,j))满足(A(i^j) equiv 0 pmod p)
分析
$11cdots 111 = {10^n-1 over 9} equiv 0pmod p $
等价于(10^n equiv 1pmod {9p})
当 (p = 2，5)时，显然答案为0（因为(11cdots 111) 模2或模5肯定不是0）
当 (p eq 2,5) 时，有(gcd(10,9p) = 1)，有(10^{phi(9p)} equiv 1pmod {9p})
(phi(9p))是欧拉函数，这个式子由欧拉定理可知
所以只需要找(10^i mod ~9p) 的最小循环节d，显然 (d|phi(9p)) ，所以只需要暴力找(phi(9p))的因子，找到最小的符合条件的即可
”显然成立“部分证明：
设d不是 (n = phi(9p)) 的因子，那么 (n = kd + r) , 又(10^{n} equiv 1pmod {9p}) ,(10^{d} equiv 1pmod {9p}) ，所以有(10^r equiv 1pmod {9p})，r比d小，与d最小矛盾
接下来只需要找有多少个(pair(i,j), d|i^j)
把 d 质因数分解：(d=p_1^{k_1}p_2^{k_2}cdots p_l^{k_l}), 要使得 (i^j) 是 (d) 的倍数，那么在 (i^j) 的质因数分解中 (p_1,p_2cdots p_l) 的指数中都要比(d) 中的大，所以我们考虑 j 固定的时候，有多少个 i 可以满足条件。
很容易就可以想到
(i) 必须是 (g = p_1^{lceil {k_1over j} ceil} p_2^{lceil {k_2over j} ceil}cdots p_l^{lceil {k_lover j} ceil}) 的倍数（至于为什么上取整，可以想一想，因为要求最小的 (x), 有(x*j >= k_1 && x*(j-1) < k_1) ）。因此一共有(nover g)个合法的(i)。
取(mx = max(k_1,k_2,cdots k_l)) 那么 我们只需要依次计算(j,(j in [1,mx])) 就可以了。而对于 (j > mx) 的部分，合法的 i 的个数都是一样的。不妨带入上式看一看。
计算原理就是这样。但是实际操作又遇到了一些坑..
计算(phi(9p)) 后，枚举因数找循环节时，快速幂会爆ll，所以要用快速乘（因为p最大1e9)
另一种方法是，因为欧拉函数是积性函数，所以如果9和p互质，那么(phi(9p) = phi(9) *(p-1)) ，对(p=3)的情况进行特判，而对于其他情况只需要枚举(phi(p))的因子即可。
因为当9和p互质时，若有 n 对 $10^n equiv 1pmod {9p} $成立，那么一定有(10^n equiv 1pmod {p}) 成立
代码
计算(phi(9p))快速乘方法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int n,m,p;
int q[N],c[N],tot;
ll mul(ll a, ll b, ll p) {
ll ret = 0;
while (b) {
if (b & 1) ret = (ret + a) % p;
b /= 2;
a = (a + a) % p;
}
return ret;
}
ll ksm(ll a,ll b,ll mod){
ll res = 1;
for(;b;b>>=1){
if(b&1)res = mul(res,a,mod);
a = mul(a,a,mod);
}
return res;
}
ll getphi(ll x){
ll res = x;
for(ll i=2;i*i <= x;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;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d",&p,&n,&m);
if(p == 2 || p == 5){
puts("0");
continue;
}
ll phi = getphi(9ll * p);
ll fac = 1e18;
for(ll i=2;i*i<=phi;i++){
if(phi % i == 0){
if(ksm(10,i,p * 9ll) == 1)fac = min(fac,i);
if(ksm(10,phi/i,p * 9ll) == 1)fac = min(fac,phi/i);
}
}
tot = 0;
for(int i=2;i*i<=fac;i++){
if(fac % i == 0){
q[++tot] = i;c[tot] = 0;
while(fac % i == 0)fac /= i,c[tot] ++;
}
}
if(fac > 1)q[++tot] = fac,c[tot] = 1;
ll res = 0;
int mx = 0;
for(int i=1;i<=tot;i++) mx = max(mx,c[i]);
for(int j=1;j <= mx && j <= m;j++){
int now = 1;
for(int i=1;i<=tot;i++){
int k = c[i] / j + (c[i]%j != 0);
for(int o = 1;o<=k;o++)now *= q[i];
}
res += n / now;
}
if(m > mx){
int now = 1;
for(int i=1;i<=tot;i++)now *= q[i];
res += 1ll * (m-mx) * (n / now);
}
printf("%lld
",res);
}
return 0;
}
标程用的方法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<pair<int, int> > plist;
int pow_mod(int x, int k, int p)
{
int ret = 1;
for (; k; k>>=1)
{
if (k&1) ret = 1LL*ret*x%p;
x = 1LL*x*x%p;
}
return ret;
}
int f(int n, int k)
{
int d = 1;
for (auto pv: plist)
{
int t = (pv.second+k-1) / k;
while (t--) d *= pv.first;
}
return n/d;
}
int main()
{
int T, n, m, p, d, D;
scanf("%d", &T);
while (T--)
{
scanf("%d %d %d", &p, &n, &m);
if (p == 2 || p == 5) {puts("0"); continue;}
if (p == 3) // 10^d = 1 mod 27 特判p = 3
{
//phi(27) = 18
D = 18;
p = 27;
}
else D = p-1;
assert(pow_mod(10, D, p) == 1);
d = 1e9;
for (int i = 1; i*i <= D; ++i)
{
if (D % i) continue;
if (pow_mod(10, i, p) == 1)
d = min(d, i);
if (pow_mod(10, D/i, p) == 1)
d = min(d, D/i);
}
for (int i = 2; i*i <= d; ++i)
{
if (d % i) continue;
int c = 0;
while (d % i == 0) ++c, d /= i;
plist.push_back(make_pair(i, c));
}
if (d != 1) plist.push_back(make_pair(d, 1));
LL ans = 0;
for (int i = 1; i <= 30 && i <= m; ++i)
ans += f(n, i);
if (m > 30) ans += 1LL*(m-30)*f(n, 30);
printf("%lld
", ans);
plist.clear();
}
return 0;
}