HDU4947

HDU4947

题目大意:

给你一个长度为 l l l的数组, q q q次操作:

1 1 1 让每个满足 g c d ( i , n ) = d gcd(i,n)=d gcd(i,n)=d的位置 i i i上加 v v v.
2 2 2 查询前缀和 [ 1 , x ] [1,x] [1,x].

题目思路:

修改:

考虑对于每个 i i i有式子:
a i = v ∗ [ g c d ( i , n ) = d ] a_i=v*[gcd(i,n)=d] ai​=v∗[gcd(i,n)=d]
a i = v ∗ [ g c d ( i d , n d ) = 1 ] a_i=v*[gcd(\frac id,\frac nd)=1] ai​=v∗[gcd(di​,dn​)=1]
= ∑ p ∣ g c d ( i d , n d ) v ∗ μ ( p ) =\sum_{p|gcd(\frac id,\frac nd)}^{}v*\mu(p) =∑p∣gcd(di​,dn​)​v∗μ(p)
= ∑ p ∣ i d , p ∣ n d v ∗ μ ( p ) =\sum_{p|\frac id,p| \frac nd}^{}v*\mu(p) =∑p∣di​,p∣dn​​v∗μ(p)
= ∑ p d ∣ i , p ∣ n d v ∗ μ ( p ) =\sum_{pd|\frac i,p| \frac nd}^{}v*\mu(p) =∑pd∣,i​p∣dn​​v∗μ(p)

由于 n d \frac nd dn​是已知量,所以我们可以枚举 p ∣ n d p|\frac nd p∣dn​.对于每个确定的 p p p.
我们构造 f p d + = v ∗ μ ( p ) f_{pd}+=v*\mu(p) fpd​+=v∗μ(p)

那么这个时候 a i = ∑ j ∣ i f j a_i=\sum_{j|i}^{}f_j ai​=∑j∣i​fj​

查询:

∑ i = 1 x a i = ∑ i = 1 x ∑ j ∣ i f j = ∑ j = 1 x f j ∗ ⌊ x j ⌋ \sum_{i=1}^{x}a_i=\sum_{i=1}^{x}\sum_{j|i}^{}f_j=\sum_{j=1}^{x}f_j*\lfloor \frac xj \rfloor ∑i=1x​ai​=∑i=1x​∑j∣i​fj​=∑j=1x​fj​∗⌊jx​⌋

分块+树状数组维护即可.

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int u[maxn] , id[maxn] , bk[maxn] , p[maxn] , cnt;
ll sum[maxn];
int l;
ll lowbit(ll x){return x & -x;}
void add(ll x,ll c){while(x<=l){sum[x] += c;x += lowbit(x);}}
ll ask(ll x){ll ans=0;while(x){ans+=sum[x];x-=lowbit(x);}return ans;}
vector<int> f[maxn];
void init ()
{u[1] = 1;for (int i = 2 ; i < maxn ; i++){if (!bk[i]){p[++cnt] = i;u[i] = -1;}for (int j = 1 ; j <= cnt && i * p[j] < maxn ; j++){bk[i * p[j]] = 1;if (i % p[j] == 0) {u[i * p[j]] = 0;break;}else {u[i * p[j]] = -u[i];}}}for (int i = 1 ; i < maxn ; i++)for (int j = i ; j < maxn ; j += i)f[j].pb(i);return ;
}
int main()
{ios::sync_with_stdio(false);init();int q , cnt = 0;while (cin >> l >> q , l || q){for (int i = 1 ; i <= l ; i++) sum[i] = 0;cout << "Case #" << (++cnt) << ":" << endl;for (int i = 1 ; i <= q ; i++){int op; cin >> op;if (op == 1){int n , d , v; cin >> n >> d >> v;if (n % d) continue;for (auto p : f[n / d]) add(p * d , 1ll * v * u[p]);}else {int x; cin >> x;ll ans = 0;for (int ls = 1 , r ; ls <= x ; ls = r + 1){r = x / (x / ls);ll a = ask(r) - ask(ls - 1);ans += a * (x / ls);}cout << ans << endl;}}}return 0;
}