JZOJ 5026 Number

发表于 | 分类于 | 10

首先有一个结论：当 n 有平方质因子时，除非 n=4，否则有无数解。

一个并不严谨的证明：
设 n=m∏i=1pcii,x=km∏i=1pci+c′ii，其中 gcd(n,k)=1。
则 σ0(x)=σ0(k)∏i=1(ci+c′i+1)。
对于 1≤i≤m，考虑关于 c′i 的方程 pcii=ci+c′i+1。
对于其解 c′i=x0，设 d=ci+x0+1pi。注意到除非 ci=1 或 pi=ci=2，一定仍存在 x′0 满足 c0+x′0+1=d，此时便可将一个 pi 的贡献加入到 k 中，并且易知这样的 k 有无数种。
而若 pi=ci=2，易证除非 m=1，否则亦有无数解。

首先 Pollard-Rho 分解质因子，然后容易发现 m≤15，考虑用一个简单的状压 DP 统计答案。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tr1/unordered_set>
using namespace std;
using namespace tr1;
const int CNT = 1e7;
const int M = 15;
unordered_set<long long> vis;
inline long long fmul(long long a,long long b,long long mod)
{
    return (a * b - (long long)((long double)a / mod * b) * mod + mod) % mod;
}
inline long long fpow(long long a,long long b,long long mod)
{
    long long ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = fmul(ret,a,mod)),a = fmul(a,a,mod);
    return ret;
}
inline bool witness(long long x,long long p)
{
    if(fpow(x,p - 1,p) ^ 1)
        return 0;
    long long k = p - 1;
    while(!(k & 1))
    {
        k >>= 1;
        long long t = fpow(x,k,p);
        if((t ^ 1) && (t ^ p - 1))
            return 0;
        if(t == p - 1)
            return 1;
    }
    return 1;
}
inline bool Miller_Rabin(long long n)
{
    if(n == 1)
        return 0;
    const int base[] = {2,3,7,61,24251,19260817};
    for(register int i = 0;i < 6;++i)
        if(n == base[i])
            return 1;
        else if(!witness(base[i],n))
            return 0;
    return 1;
}
bool Pollard_Rho(long long n)
{
    if(Miller_Rabin(n))
    {
        if(vis.count(n))
            return 0;
        vis.insert(n);
        return 1;
    }
    const long long c = 1e9 + 9;
    const int k = 200;
    long long t1 = 1e9 + 7;
    long long t2 = (fmul(t1,t1,n) + c) % n;
    long long p = 1;
    int i = 0;
    while(t1 ^ t2)
    {
        ++i,p = fmul(p,abs(t1 - t2),n);
        if(!p)
        {
            long long d = __gcd(abs(t1 - t2),n);
            return Pollard_Rho(d) && Pollard_Rho(n / d);
        }
        if(!(i % k))
        {
            long long d = __gcd(p,n);
            p = 1;
            if((d ^ 1) && (d ^ n))
                return Pollard_Rho(d) && Pollard_Rho(n / d);
        }
        t1 = (fmul(t1,t1,n) + c) % n,t2 = (fmul(t2,t2,n) + c) % n,t2 = (fmul(t2,t2,n) + c) % n;
    }
    long long d = __gcd(p,n);
    if((d ^ 1) && (d ^ n))
        return Pollard_Rho(d) && Pollard_Rho(n / d);
}
int T;
long long n,mod;
int prime[CNT + 5],cnt,bz[CNT + 5];
int m,full;
long long p[M + 5],f[(1 << M) + 5];
int main()
{
    freopen("number.in","r",stdin),freopen("number.out","w",stdout);
    for(register int i = 2;i <= CNT;++i)
    {
        if(!bz[i])
            prime[++cnt] = i;
        for(register int j = 1;j <= cnt && i * prime[j] <= CNT;++j)
        {
            bz[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%d",&T);
    for(int flag;T;--T)
    {
        scanf("%lld%lld",&n,&mod);
        if(n == 4)
        {
            printf("%lld\n",8 % mod);
            continue;
        }
        vis.clear(),flag = 0;
        for(register int i = 1;i <= cnt && prime[i] <= n;++i)
            for(;!(n % prime[i]);n /= prime[i])
                if(vis.count(prime[i]))
                    flag |= 1;
                else
                    vis.insert(prime[i]);
        if(flag || (n > 1 && !Pollard_Rho(n)))
        {
            puts("-1");
            continue;
        }
        memset(f,0,sizeof f),m = 0,f[0] = 1;
        for(register unordered_set<long long>::iterator it = vis.begin();it != vis.end();++it)
            p[++m] = *it;
        full = (1 << m) - 1;
        for(register int i = 0;i <= full;++i)
            for(register int j = 1;j <= m;++j)
                if(!(i & (1 << j - 1)))
                    f[i | (1 << j - 1)] = (f[i | (1 << j - 1)] + fmul(f[i],fpow(p[__builtin_popcount(i) + 1] % mod,p[j] - 1,mod),mod)) % mod;
        printf("%lld\n",f[full]);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment