hdu 5212 : Code【莫比乌斯】
2024-10-04 05:25:04
题给代码可以转化为下面的公式
然后用F[n]记录公约数为n的(a[i],a[j])对数,用f[n]记录最大公约数为n的(a[i],a[j])对数
之后枚举最大公约数d
至于求F[n],可以先将1~10000全部因数分解,用num[i]记录约数中包含i的a[x]的个数。对每一个a[i],其每一个约数都对对应的num[i]贡献了1 。显然,F[n]=num[n]*num[n]
#include<bits/stdc++.h> using namespace std; typedef long long LL; ; const int maxn=1e6; ]; ]; ]; void init() { mu[]=; ; ;i<=maxn;i++) { if(!check[i]) { prime[tot++]=i; mu[i]=-; } ;j<tot;j++) { if(i*prime[j]>maxn) break; check[i*prime[j]]=true; ) { mu[i*prime[j]]=; break; } else { mu[i*prime[j]]=-mu[i]; } } } } int n; ]; LL num[]; vector<]; LL f[]; LL F[]; void init1() { ;i<=;i++) { int j; ;j*j<i;j++) ) { fac[i].push_back(j); fac[i].push_back(i/j); } if(j*j==i) fac[i].push_back(j); sort(fac[i].begin(),fac[i].end()); } } void add(int x) { ;i<fac[x].size();i++) num[fac[x][i]]++; } int gcd(int a,int b) { return b? gcd(b,a%b): a; } //int calc() //{ // int res=0; // for(int i=1; i<=n; i++) // for(int j=1; j<=n; j++) // { // res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1); // res%=10007; // } // return res; //} int main() { init(); init1(); while(~scanf("%d",&n)) { memset(num,,sizeof(num)); memset(f,,sizeof(f)); ;i<=n;i++) { scanf("%d",&a[i]); add(a[i]); } LL ans1=,ans2=; ;i<=;i++) F[i]=num[i]*num[i]; ;i<=;i++) ;i*j<=;j++) f[i]=(f[i]+mu[j]*F[i*j])%mod; ;i<=;i++) { ans1=(ans1+f[i]*i*i)%mod; ans2=(ans2+f[i]*i)%mod; } printf("%lld\n",((ans1-ans2)%mod+mod)%mod); // cout<<calc()<<endl; } }
最新文章
- String驻留带来的危害
- java继承、抽象和接口
- tyvj1089 smrtfun
- Java中基本数据类型的对比记忆
- Oracle 表空间联机(online)与脱机(offline)
- [PHP] 读取大文件并显示
- js实现把网页table导成Excel
- linux,shell输入反斜杠显示&#39;W&#39;。
- Oracle 热备份batch脚本 Windows
- C# 绘制统计图(柱状图, 折线图, 扇形图)
- 3D游戏引擎一 win32编程
- Cgroup maintainer丽泽范:解剖Linux核心容器技术
- 分割字节流为G,MB,KB的算法
- 1.7Oob封装 继承 访问修饰符 静态和构造方法的执行顺序
- 换工作之后需要兼容ie8的我
- php opcodes运行原理
- urllib库
- call apply bind 区别?
- java-IO流-字符流-FileReader、FileWriter、自定义小数组的拷贝、BufferedReader、BufferedWriter、readLine()和newLine()方法、LineNumberReader、使用指定的码表读写字符
- 一个可遇不可求的 bug 全局变量初始化顺序问题 哈哈