[51nod]1678 lyk与gcd(莫比乌斯反演)
2024-08-24 11:58:14
题面
题解
和这题差不多
//minamoto
#include<bits/stdc++.h>
#define R register
#define pb push_back
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=1e5+5;
typedef long long ll;
vector<int>vec[N];int mu[N],p[N],vis[N],a[N],n,q,m;ll f[N];
void init(int n=N-5){
mu[1]=1;
fp(i,2,n){
if(!vis[i])p[++m]=i,mu[i]=-1;
for(R int j=1;j<=m&&1ll*i*p[j]<=n;++j){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
mu[i*p[j]]=-mu[i];
}
}
fp(i,1,n)if(mu[i])for(R int j=i;j<=n;j+=i)vec[j].pb(i);
}
int main(){
// freopen("testdata.in","r",stdin);
init();n=read(),m=read();
fp(i,1,n)a[i]=read();
fp(i,1,n)for(R int j=i;j<=n;j+=i)f[i]+=a[j];
for(int op,x,y;m;--m){
op=read(),x=read();
if(op&1){
y=read();if(a[x]==y)continue;
fp(i,0,vec[x].size()-1)if(mu[vec[x][i]])f[vec[x][i]]+=y-a[x];
a[x]=y;
}else{
ll res=0;
fp(i,0,vec[x].size()-1)if(mu[vec[x][i]])res+=f[vec[x][i]]*mu[vec[x][i]];
printf("%lld\n",res);
}
}
return 0;
}
最新文章
- golang笔记——并发
- PL/SQL之--触发器
- const变量赋值报错分析
- 将Windows上的文件上传到Linux上
- sublime text 几种常用插件
- svn unable to connect to a repository at url 执行上下文错误 不能访问SVN服务器问题
- windows phone 7 通过Post提交URL到服务器,从服务器获取数据(比如登陆时候使用)
- css3渐变 transition使用方法
- Docker常用名称
- UOJ#185. 【ZJOI2016】小星星 容斥原理 动态规划
- list quen队列
- python_代码中调用java类
- 函数和常用模块【day06】:datetime模块(二)
- php5.6.40编译安装
- 拦截导弹问题(NOIP1999)
- 大数字运算, BigInteger
- unlimited channel buffer in Go
- 51nod2004 终结之时 (支配树+树剖+树链的并)
- 天嵌IMX6开发板测试-第一篇
- Linux内核设计笔记11——定时器
热门文章
- php.ini中date.timezone设置分析
- noip模拟赛 写代码
- noip模拟赛 道路分组
- 创建Django项目(四)——模型
- Evaluate Reverse Polish Notation(逆波兰式)
- WebLogic(12C)——简单公布和JDBC
- 域名添加HTTPS
- CentOS 查看日志命令
- Xcode iOS9.3 配置包 iOS10.0 配置包 iOS10.2 配置包 could not find developer disk image
- JAVA进阶-网络编程