hdu 5212 Code 筛法或者莫比乌斯
2024-08-25 06:28:12
Code
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?
The function:
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;
}
Input
There are Multiple Cases.(At MOST 10)
For each case:
The first line contains an integer N(1≤N≤10000).
The next line contains N integers a1,a2,...,aN(1≤ai≤10000).
Output
For each case:
Print an integer,denoting what the function returns.
Sample Input
5
1 3 4 2 4
1 3 4 2 4
Sample Output
64
Hint
gcd(x,y) means the greatest common divisor of x and y.
Source
先占坑,晚点补莫比乌斯
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e4+,M=1e6+,inf=1e9+;
const LL INF=1e18+,mod=1e9+; int cnt[N],sum[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(cnt,,sizeof(cnt));
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
cnt[x]++;
}
for(int i=;i<=;i++)
{
for(int j=i;j<=;j+=i)
sum[i]+=cnt[j];
sum[i]=sum[i]*sum[i];
}
LL ans=;
for(int i=;i>=;i--)
{
for(int j=i+i;j<=;j+=i)
sum[i]-=sum[j];
//if(sum[i])cout<<i<<" "<<sum[i]<<endl;
ans+=1LL*i*(i-)*sum[i];
ans%=;
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- 各种Android手机Root方法
- [OpenCV] Convolutional Neural Network
- linux-ntpdate同步更新时间
- Hololens开发笔记之Gesture手势识别(Manipulation手势控制物体旋转)
- 【BZOJ-4569】萌萌哒 ST表 + 并查集
- OpenCV图像轮廓检测
- objective C 学习之02
- [HIHO1196]高斯消元&#183;二(高斯消元、枚举自由变元)
- Poj 1001 / OpenJudge 2951 Exponentiation
- hdu 1005解题报告
- 给自己的QQ群开启腾讯官方的群聊机器人
- windows调试工具列表
- 在同一个sql语句中,统计不同条件的Count数量
- 基于 socket.io 的 AI 服务 杂谈
- 十九、多文件上传(ajaxFileupload实现多文件上传功能)
- 【cf842D】Vitya and Strange Lesson(01字典树)
- HTTP 599: SSL certificate problem: unable to get local issuer certificate错误
- JDBC(13)—JDBC调用存储过程和函数
- 使用docker compose编排容器
- 9.7 翻译系列:EF数据注解特性之--InverseProperty【EF 6 Code-First系列】