admin管理员组文章数量:1612098
H - Curious
Gym - 102800H
题意:给你T组样例,给n, m, k, n代表数组元素个数,m代表数组元素值最大值,k代表询问个数,然后给你n个元素值a[i], k层询问,每层询问给你一个x 问 个数
思路:
h(x) 就是 1~n 中的元素值取余x的个数。f(x) = h^2(x), 比如3个元素2 4 6 ,d为2, 那f(d) = 9 (2和2匹配,2和4,2和6,4和2,4和4,4和6,6 和2,6和4,6和6)。
所以 𝑔(𝑑) = ∑ 𝑑|𝑥 𝑓 (𝑥)𝜇( 𝑥 𝑑 )。
#include<bits/stdc++.h>
#define up(i, a, b) for(int i = a; i <= b; i++)
#define down(i, a, b)for(int i = a;i >= b; i--)
#define mem(a, b)memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn = 1e5 + 700;
int mu[maxn], prim[maxn], vis[maxn] = {1,1}, prime_sum = 0;
void init(int n){
mu[1] = 1;
up(i, 2, n){
if(vis[i]==0)prim[++prime_sum] = i, mu[i] = -1;
for(int j = 1;prim[j]*i <= n && j <= prime_sum; j++){
vis[prim[j]*i] = 1;
if(i%prim[j] == 0){
break;
}
else mu[prim[j]*i] = -mu[i];
}
}
}
vector<int> v[maxn];
void get(int n){
up(i, 1, n){
for(int j = 1; j * j <= i; j++){
if(i % j == 0){
v[i].push_back(j);
if(j*j != i)v[i].push_back(i / j);
}
}
}
}
int arr[maxn], exist[maxn], num[maxn], dp[maxn];
signed main()
{
init(100005);
get(100005);
int T;
scanf("%lld", &T);
while(T--){
int n, m, k;
scanf("%lld%lld%lld", &n, &m, &k);
up(i, 1, 100300)exist[i] = 0, dp[i] = -1;
up(i, 1, n){
scanf("%lld", &arr[i]);
exist[arr[i]]++;
}
int x;
while(k--){
scanf("%lld", &x);
if(dp[x] != -1){printf("%lld\n", dp[x]);continue;}
int len = 0, res = 0;
for(int j = 1;j <= m; j++){
int X = j*x;
if(X > m)break;
len = j;
for(auto g : v[j]){
num[g] += exist[X];
}
}
//求h(x)这里比较巧妙,
//j的因子必被 j*x 整除,所以 看j*x有多少arr值,即arr % (j*x)有多少个,一直累加
//
up(i, 1, len)res += num[i]*num[i]*mu[i], num[i] = 0;
//1倍到len倍
dp[x] = res;//记忆化
printf("%lld\n", res);
}
}
return 0;
}
/*
2
5 5 5
1 2 3 4 5
1
2
3
4
5
5 5 5
1 2 3 4 5
1
2
3
4
5
*/
版权声明:本文标题:Problem H. Curious (莫比乌斯反演) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728630923a1167072.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论