当前位置: 首页 > news >正文

没做完的题

放在这里待办
定义

\[g(n)=2\sum ^n_{i=2}\left \lfloor \frac{n}{i} \right \rfloor^2 \phi(i)+n^2 \]

\(g(n)\)

定义

\[f(n)=\frac{g(n)-n^2}{2} \]

\[f(n)=\sum ^n_{i=2}\left \lfloor \frac{n}{i} \right \rfloor^2 \phi(i) \]

\[f(n-1)=\sum ^{n-1}_{i=2}\left \lfloor \frac{n-1}{i} \right \rfloor^2 \phi(i) \]

\[f(n)-f(n-1)=\sum ^{}_{i|n}((\frac {n}{i})^2-(\frac {n}{i}-1)^2)\phi(i) \]

\[=2\sum ^{}_{i|n}\frac {n}{i}\phi(i) - n \]

定义

\[g(n)=2f(n)+n^2 \]

\[sum_g=2sum_f+\frac{n(n+2)(2n+1)}{6} \]

#include<bits/stdc++.h>//记得开int128
#define int long long
#define ll __int128
using namespace std;
const int N=1e7+5;
int p[N],cnt,phi[N],s[N],low[N],T,sum[N],sums[N];
bool isp[N];
unordered_map<int,int>ans;
void Euler(int n){s[1]=low[1]=phi[1]=isp[1]=sum[1]=1;for(int i=2;i<=n;i++){if(!isp[i])p[++cnt]=i,phi[i]=i-1,s[i]=2*i-1,low[i]=i;sum[i]=sum[i-1]+phi[i],sums[i]=sums[i-1]+2*s[i]-i;for(int j=1;j<=cnt&&i*p[j]<=n;j++){isp[i*p[j]]=1;if(i%p[j]==0){low[i*p[j]]=low[i]*p[j],phi[i*p[j]]=phi[i]*p[j];if(low[i]==i){s[i*p[j]]=s[i]*p[j]+phi[i*p[j]];}else{s[i*p[j]]=s[i/low[i]]*s[low[i]*p[j]];}break;}low[i*p[j]]=p[j],s[i*p[j]]=s[i]*s[p[j]],phi[i*p[j]]=phi[i]*phi[p[j]];}}for (int i=1;i<=10;i++) cout<<s[i]<<" "; cout<<"\n";
}
int djs(int n){if(n<=N-5)return sum[n];if(ans[n])return ans[n];__int128 res=(__int128)n*(n+1)/2;for(int l=2,r;l<=n;l=r+1){r=n/(n/l);res-=(r-l+1)*djs(n/l);}return ans[n]=res;
}
signed main(){freopen("1.in","r",stdin);// freopen("1.out","w",stdout);cin>>T;Euler(N-5);while(T--){int n;cin>>n;if(n<=N-5){cout<<2*s[n]+n*n<<endl;continue;}int res=0;for(int l=1,r;l<=n;l=r+1){r=n/(n/l);res+=(djs(r)-djs(l-1))*(n/l)*(n/l);}cout<<2*res-n*n<<endl;}
}
http://www.hskmm.com/?act=detail&tid=28273

相关文章:

  • 第十一天
  • JavaScriptDay1
  • 淘宝NPM镜像地址https://registry.npm.taobao.org不可用
  • 星星充电一面
  • 6 CF1034 div3 题解
  • 5 ABC413 题解
  • 4 CF 1032 div3 题解
  • 3 ABC411 C ~ E题解
  • 9 ABC408 D~F 题解
  • 8 ABC425 G 题解
  • 智能防御,安全赋能:AI-FOCUS 滤海AI DLP 化解外部 AI 风险
  • IDEA快捷键
  • VS code 中代码补全 自动补全函数括号
  • 优先队列
  • 学习ReAct并使用langgraph实现一个简单的ReAct AI Agent!!
  • abc 408 d~f
  • RMQ与LCA学习笔记
  • mamba-硬件感知算法
  • Java1
  • 完整教程:lua代码解析1
  • 二维数点
  • gitee和github如何修改仓库名并且保持与原远程仓库的连接?(手把手教学) - 实践
  • 2025.10.10总结 - A
  • [20251010]建立完善tpt的prr.sql脚本.txt
  • 第十一篇
  • testtest
  • 题解:AT_arc138_f [ARC138F] KD Tree
  • SP33 TRIP - Trip 个人题解
  • 经营不是老板一个人的事 - 智慧园区
  • Codeforces Round 1051 (Div. 2)[A ~E]