首页 > 代码库 > 51nod 1678 lyk与gcd
51nod 1678 lyk与gcd
这天,lyk又和gcd杠上了。
它拥有一个n个数的数列,它想实现两种操作。
1:将 ai 改为b。
2:给定一个数i,求所有 gcd(i,j)=1 时的 aj 的总和。
Input
第一行两个数n,Q(1<=n,Q<=100000)。 接下来一行n个数表示ai(1<=ai<=10^4)。 接下来Q行,每行先读入一个数A(1<=A<=2)。 若A=1,表示第一种操作,紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。 若B=2,表示第二种操作,紧接着一个数i。(1<=i<=n)。
Output
对于每个询问输出一行表示答案。
Input示例
5 3 1 2 3 4 5 2 4 1 3 1 2 4
Output示例
9 7
方法1:
考虑辅助数组f[i]表示所有下标为i的倍数的a数组的总和。
例如有5个数,那么f[1]=a[1]+a[2]+a[3]+a[4]+a[5],f[2]=a[2]+a[4],f[3]=a[3],f[4]=a[4],f[5]=a[5]。
对于每一个修改操作,我们只需要求出i的所有因数,然后将下标为它的因数的f数组中修改值即可。
对于所有询问操作,求出i的所有因数p1,p2,p3...之后答案即为Σu[pi]*f[pi]。
其中u为mobius函数。
总复杂度为所有操作中i的因数个数总和。
方法2:
比较基础的容斥题,我们预处理出每个i的所有素因子的组合,比如6={2,3,6},那么我们对于a[6]将它加入到sum[2],sum[3],sum[6]中,统计答案时用容斥思想加加减减就行了。O(nlogn)
#include<map> #include<set> #include<cmath> #include<queue> #include<bitset> #include<math.h> #include<vector> #include<string> #include<stdio.h> #include<cstring> #include<iostream> #include<algorithm> #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=100010; const int MAX=1000000100; const int mod=100000000; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=1000000007; const int INF=1000000010; const double pi=acos(-1.0); typedef double db; typedef unsigned long long ull; vector<int>f[N]; vector<int>g[N]; int a[N],q[N]; ll sum[N]; void deal(int n) { int i,j,h,w,k=0; for (i=2;i<=n;i++) { if (!q[i]) a[++k]=i; for (j=1;j<=k;j++) { if (a[j]*i>n) break ; q[a[j]*i]=1; if (i%a[j]==0) break ; } } for (i=1;i<=k;i++) for (j=a[i];j<=n;j+=a[i]) { w=f[j].size(); for (h=0;h<w;h++) { f[j].push_back(f[j][h]*a[i]);g[j].push_back(g[j][h]+1); } f[j].push_back(a[i]);g[j].push_back(1); } } int main() { int i,j,n,q,x,y; ll ans; scanf("%d%d", &n, &q); deal(n); for (i=1;i<=n;i++) { scanf("%d", &a[i]);sum[1]+=a[i]; for (j=0;j<f[i].size();j++) sum[f[i][j]]+=a[i]; } while (q--) { scanf("%d", &x); if (x==1) { scanf("%d%d", &x, &y); for (i=0;i<f[x].size();i++) sum[f[x][i]]-=a[x]; sum[1]-=a[x];a[x]=y;sum[1]+=a[x]; for (i=0;i<f[x].size();i++) sum[f[x][i]]+=a[x]; } else { ans=sum[1]; scanf("%d", &x); for (i=0;i<f[x].size();i++) if (g[x][i]&1) ans-=sum[f[x][i]]; else ans+=sum[f[x][i]]; printf("%lld\n", ans); } } return 0; }
51nod 1678 lyk与gcd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。