LOJ #6539 奇妙数论题
2024-09-23 22:05:30
不想咕太久..就随便找个题更一下
题意
求题面里那个式子
题解
有一个常用的小式子
$$\sum_{x|a,x|b}\varphi(x)=\gcd(a,b)$$
用这个式子直接对题面的式子进行化简
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n(a_i,a_j)·(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n(\sum_{x|i,x|j}\varphi(x))(a_i,a_j)\\
&=\sum_{x=1}^n\varphi(x)\sum_{x|i}\sum_{x|j}(a_i,a_j)
\end{aligned}
$$
枚举x,相当于求一个大小为$ \frac{n}{x}$的集合内两两$ \gcd$的和
再用一次最上面的式子优化
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n\gcd(a_i,a_j)\\
&=\sum_{d=1}^n\varphi(d)(\sum_{i=1}^n[d|a_i])^2
\end{aligned}
$$
预处理每个数的约数,每次暴力计算
复杂度是对的..跑的飞快...
代码
小范围暴力抢了rk1
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
#define N 100000
bool pri[N+];int ss[N+],phi[N+];
void init(){
phi[]=;
for(rt i=;i<=N;i++){
if(!pri[i]) ss[++cnt]=i,phi[i]=i-;
for(rt j=;j<=cnt&&i*ss[j]<=N;j++){
phi[i*ss[j]]=phi[i]*phi[ss[j]];
pri[i*ss[j]]=;
if(i%ss[j]==){
phi[i*ss[j]]=phi[i]*ss[j];
break;
}
}
}
}
int a[],sum[];
vector<int>ys[];
ll calc2(int x){
ll ret=;
for(rt i=x;i<=n;i+=x)sum[a[i]]++;
for(rt i=;i<=n;i++){
int now=;
for(rt j=i;j<=n;j+=i)now+=sum[j];
ret+=1ll*phi[i]*now*now;
}
for(rt i=x;i<=n;i+=x)sum[a[i]]=;
return ret;
}
ll calc(int x){
ll ret=;
for(rt i=x;i<=n;i+=x){
for(auto j:ys[a[i]]){
ret+=(sum[j]*+)*phi[j];
sum[j]++;
}
}
for(rt i=x;i<=n;i+=x){
for(auto j:ys[a[i]])sum[j]=;
}
return ret;
}
int main(){
init();n=read();
for(rt i=;i<=n;i++)a[i]=read();
for(rt i=;i<=n;i++)
for(rt j=i;j<=n;j+=i)ys[j].push_back(i);
ll ans=;
for(rt x=;x<=n;x++){
if(x<=)ans+=1ll*phi[x]*calc2(x);else
ans+=1ll*phi[x]*calc(x);
}
cout<<ans%;
return ;
}
最新文章
- 新编码神器Atom使用纪要
- Xamarin.Android之简单的抽屉布局
- 游戏AI框架
- [Cocos2d-x For WP8]Layer 层
- 【POJ】2828 Buy Tickets(线段树+特殊的技巧/splay)
- 【转发】centos 7安装完后出现please make your choice from &#39;1&#39; ......
- Linux下MySQL5.6的修改字符集编码为UTF8
- yar
- Java设计模式12:常用设计模式之外观模式(结构型模式)
- css设置文字不换行,超过的部分用“...”代替
- 【有源汇上下界费用流】BZOJ 3876 [Ahoi2014]支线剧情
- Splay POJ3468(老题新做)
- Python之路:Python 基础(三)-文件操作
- 安装TensorFlow的步骤
- Loadrunner之脚本的调试和保存(六)
- 未能加载文件或程序集“ .....WebUI ”或它的某一个依赖项,试图加载格式不正确的程序
- 【23】备忘录模式(Memento Pattern)
- 在TensorFlow中运行程序多次报错:AttributeError: __exit__
- Django 模板继承extend 标签include block
- 重新学习之spring第一个程序,配置IOC容器