【2020年牛客暑假第九场】E题 Groundhog Chasing Death

传送门：https://ac.nowcoder.com/acm/contest/5674/E

题意

$求\prod_{i=a}^b\prod_{i=c}^dgcd(x^i, y^j) mod998244353的值$

思路

观察上式，我们知道$gcd$是$x,y$的所有质因子个数的$min(a,b)$，即$gcd(x,y)=\sum_{i=1}^np_i^{min(ai,bi）}$（ai,bi分别是x,y公共质因子的次幂） 所以，我们可以统计$x,y$的每个公共质因子的次幂，然后再全部整合累乘得出答案。

一步一步分析： 要求$\prod_{i=a}^b \prod_{i=c}^dgcd(x^i, y^j)$ 其实求的就是$\prod_{px ,py}p_k^{\sum_{i=a}^{b}\sum_{j=c}^dmin(Ai,Bj)}$(A,B分别为x,y分解出质因子p的次幂) 先统计x,y所有的公共质因子的次幂，然后再累乘即可 所以我们可以先质数筛把\sqrt{1e9}以内的所有质数筛出来，所以范围我定为2e5以内的质数了，然后再分解x和y的质因子，分别把公共质因子p和该因子的次幂cx,cy存在数组里，方便下面步骤的实现 然后单独分析单个公共质因子p，得$p^{\sum_{i=a}^b\sum_{j=c}^d min(Ai,Bj)}$ $先比较Ai和Bj的大小：$ $\qquad当Ai \leq Bj时，即j \geq \left \lceil \frac{Ai}{B}\right \rceil，p^{min(Ai,Bj)}=p^{Ai}$ $\qquad当Ai > Bj时，即j < \left \lceil \frac{Ai}{B}\right \rceil，p^{min(Ai,Bj)}=p^{Bj}$

接下来就有两种求解方式了，实质上是一种，只不过枚举顺序有点变化而已。

方法一：先枚举$i$再枚举公共质因子

这个方法有点一小麻烦，理解有点困难。

因为先把$i$确定下来之后，$j$也就确定下来了，因为$j= \left \lceil \frac{Ai}{B}\right \rceil$。 再来看这个式子：$\sum_{i=a}^{b}\sum_{j=c}^dmin(Ai,Bj)$ 因为枚举的是$i$，并且$j$已经确定了，再根据大小比较，所以上面的式子就是两种变化：$$\sum_{i=a}^{b}\sum_{j=max(\left \lceil \frac{Ai}{B}\right \rceil,c)}^dAi$$ $$\sum_{i=a}^{b}\sum_{j=c}^dBj$$ 所以就有以下三种情况： $\qquad 当j<c时，\sum_{i=a}^{b}\sum_{j=c}^dmin(Ai,Bj)=Ai*(d+c-1)$

$\qquad 当j>d时，\sum_{i=a}^{b}\sum_{j=c}^dmin(Ai,Bj)=B*\frac{(c+d)*(d-c+1)}{2}$

$\qquad 当c\leq j \leq d时，\sum_{i=a}^{b}\sum_{j=c}^dmin(Ai,Bj)=Ai*(d-j+1)+B*\frac{(j+c-1)*(j-c)}{2}$

当把所有的公共质因子的总次幂求出来之后就可以进行累乘得出答案，再求总次幂的过程中可以用欧拉降幂优化一下， 并且模数$998244353$正好是一个质数，所以$\varphi(998244353)=998244353-1$。

Code（286ms）

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const ll mod = 998244353;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

const int N = 2e5 + 10;

int prime[N];
bool is_prime[N];
int cnt = 0;

int px[N], cx[N], py[N], cy[N], mx, my; // 是x和y分解的质因子和质因子的次幂和质因子的个数
ll mi[N]; // 求解出来每个质因子的总次幂

struct node{
    int cx, cy;
};

vector<node> v1; // x和y的公共质因子的个数
vector<int> v2; // x和y的公共质因子的值

void sieve() // 质数筛
{
    mem(is_prime, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i < N; i++) {
        if(is_prime[i])
        {
            prime[++cnt] = i;
            for(int j = 1;j <= cnt && i * prime[j] < N; j++) {
                is_prime[i * prime[j]] = false;
                if(i % prime[j] == 0)
                    break;
            }
        }
    }
}

void Divide(ll n, int *p, int *c, int &m) // 分解质因子
{
    m = 0;
    for(int i = 2;i * i <= n; i++) {
        if(n % i == 0) {
            p[++m] = i;
            while(n % i == 0) {
                c[m]++;
                n /= i;
            }
        }
    }
    if(n > 1) {
        p[++m] = n;
        c[m] = 1;
    }
}

ll quick_pow(ll a, ll b)
{
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void solve() {
    sieve();
    ll a, b, c, d, x, y;
    scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y);

    Divide(x, px, cx, mx); // 分解x和y的质因子（值、个数）并存在数组里
    Divide(y, py, cy, my);

    int ppx = 1, ppy = 1;
    while(ppx <= mx && ppy <= my) { // 寻找x和y的公共质因子并存在数组里
        if(px[ppx] == py[ppy]) {
            v1.push_back(node{cx[ppx], cy[ppy]});
            v2.push_back(px[ppx]);
            ppx++; ppy++;
        }
        else if(px[ppx] < py[ppy]) ppx++;
        else ppy++;
    }

    for(int i = a;i <= b; i++) { // 枚举i
        for(int k = 0;k < v1.size(); k++) { // 每个质因子的个数A和B
            // int p = v2[k]; // 提取质因子
            int ccx = v1[k].cx, ccy = v1[k].cy; // 提取质因子个数
            int j = (ccx * i + ccy - 1) / ccy; // 本来是ccx*i/ccy，不过要保证向上取整，即+(B-1)/B就可以保证了，或者使用ceil()函数
            if(j < c) {
                ll t = 1ll * (d - c + 1);
                mi[k] = (mi[k] + t * i * ccx) % (mod - 1);
            }
            else if(j > d) {
                ll t = 1ll * (d + c) * (d - c + 1) / 2;
                mi[k] = (mi[k] + t * ccy) % (mod - 1);
            }
            else {
                ll t1 = 1ll * (d - j + 1);
                ll t2 = 1ll * (j - c) * (c + j - 1) / 2;
                mi[k] = (mi[k] + t1 * ccx * i) % (mod - 1);
                mi[k] = (mi[k] + t2 * ccy) % (mod - 1);
            }
        }
    }

    ll ans = 1;

    for(int i = 0;i < v1.size(); i++) {
        if(mi[i] == 0) continue;
        ans = ans * quick_pow(v2[i], mi[i]) % mod;
    }

    printf("%lld\n",ans);
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

方法二：先枚举公共质因子再枚举$i$和$j$

这个方法稍微简单一点，便于理解。

根据下面两个两个大小关系，我们可以先通过枚举每个公共质因子，然后两个循环枚举$i$和$j$比大小，确定每个质因子的总次幂即可。 $当Ai \leq Bj时，即j \geq \left \lceil \frac{Ai}{B}\right \rceil，p^{min(Ai,Bj)}=p^{Ai}$ $当Ai > Bj时，即j < \left \lceil \frac{Ai}{B}\right \rceil，p^{min(Ai,Bj)}=p^{Bj}$

所以我们可以得到下面两个式子求解公共质因子$p$的总次幂： $$\sum_{i=a}^{b}\sum_{j=max(\left \lceil \frac{Ai}{B}\right \rceil,c)}^dAi$$ $$\sum_{j=c}^{d}\sum_{i=max(\left \lceil \frac{Bj}{A}\right \rceil,a)}^bBj$$

当然，这里有几个小问题。

  • $j \geq \left \lceil \frac{Ai}{B}\right \rceil$，如果这里没有正好整除的时候，那还行，因为我们需要的时向上取整，但是如果正好整除呢，那么我们需要$j+1$即$j=\frac{Ai}{B}+1$
  • 举一个小栗子，枚举$i$的时候，因为$j=max(\left \lceil \frac{Ai}{B}\right \rceil,c)$，要是$j>d$，那么就不进行下面的操作，同理枚举$j$。

每处理一个公共质因子，把他的总次幂求解出来之后，即可将他用快速幂并加到答案$ans$里，因为可以用到欧拉降幂，所以快速幂之前的$pow1+pow2$先$mod$就不是$998244353$，而是$998244353-1$，不然会出错的。

Code (691ms)

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const ll mod = 998244353;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

const int N = 2e5 + 10;

int prime[N];
bool is_prime[N];
int cnt = 0;

int px[N], cx[N], py[N], cy[N], mx, my; // 是x和y分解的质因子和质因子的次幂和质因子的个数

struct node{
    int cx, cy;
};

vector<node> v1; // x和y的公共质因子的个数
vector<int> v2; // x和y的公共质因子的值

void sieve() // 质数筛
{
    mem(is_prime, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i < N; i++) {
        if(is_prime[i])
        {
            prime[++cnt] = i;
            for(int j = 1;j <= cnt && i * prime[j] < N; j++) {
                is_prime[i * prime[j]] = false;
                if(i % prime[j] == 0)
                    break;
            }
        }
    }
}

void Divide(ll n, int *p, int *c, int &m) // 分解质因子
{
    m = 0;
    for(int i = 2;i * i <= n; i++) {
        if(n % i == 0) {
            p[++m] = i;
            while(n % i == 0) {
                c[m]++;
                n /= i;
            }
        }
    }
    if(n > 1) {
        p[++m] = n;
        c[m] = 1;
    }
}

ll quick_pow(ll a, ll b)
{
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void solve() {
    sieve();
    ll a, b, c, d, x, y;
    scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y);

    Divide(x, px, cx, mx); // 分解x和y的质因子（值、个数）并存在数组里
    Divide(y, py, cy, my);

    int ppx = 1, ppy = 1;
    while(ppx <= mx && ppy <= my) { // 寻找x和y的公共质因子并存在数组里
        if(px[ppx] == py[ppy]) {
            v1.push_back(node{cx[ppx], cy[ppy]});
            v2.push_back(px[ppx]);
            ppx++; ppy++;
        }
        else if(px[ppx] < py[ppy]) ppx++;
        else ppy++;
    }

    ll ans = 1;

    for(int k = 0;k < v2.size(); k++) { // 枚举每个公共质因子

        ll pow1 = 0, pow2 = 0; // 下面两个循环的次幂

        for(ll i = a;i <= b; i++) { // 先枚举i
            ll j;
            if(v1[k].cx * i % v1[k].cy == 0)
                j = max(v1[k].cx * i / v1[k].cy, c);
            else
                j = max(v1[k].cx * i / v1[k].cy + 1, c); // 向上取整并且没有整除

            if(j <= d)
                pow1 = (pow1 + i * (d - j + 1) % (mod - 1)) % (mod - 1); // 欧拉降幂
        }
        pow1 = pow1 * v1[k].cx % (mod - 1); // 不要忘了系数

        for(ll j = c;j <= d; j++) { // 再枚举j

            ll i = max(v1[k].cy * j / v1[k].cx + 1, a);// 因为上面枚举i的时候处理一次重复的情况，所以这里就不需要再考虑了

            if(i <= b)
                pow2 = (pow2 + j * (b - i + 1) % (mod - 1)) % (mod - 1); // 欧拉降幂
        }
        pow2 = pow2 * v1[k].cy % (mod - 1); // 不要忘了系数

        ans = ans * quick_pow(v2[k], (pow1 + pow2) % (mod - 1)) % mod;
    }

    printf("%lld\n",ans);
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

感谢赛中和赛后牌王的“热情”指导,牌王无敌！！！

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/08/09/2020-nowcoder-shujia-9-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！