spoj 7001 Visible Lattice Points莫比乌斯反演
Description
Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.
Input :
The first line contains the number of test cases T. The next T lines contain an interger N
Output :
Output T lines, one corresponding to each test case.
Sample Input :
3
1
2
5
Sample Output :
7
19
175
Constraints :
T <= 50
1 <= N <= 1000000
题目大意:从点(0,0,0)出发的直线可看到多少个点(只能看到第一个,后面的视为挡住了看不见)。
解题思路:求gcd(x,y,z)=1的点有多少个,F(n) 表示满足条件的 gcd(x,y,z)==n的 (x,y,z) 对数;G(n) 表示满足 n | gcd(x,y,z) 的(x,y,z)对数,即 gcd(x,y,z)%n==0 的(x,y,z) 对数;
由定义:G(n)=sigma(F(d)),F(n)=sigma(U(d/n)*G(d))
这题就是求F(1)。G(d)=(n/d)*(n/d)(n/d)。
当3个坐标为0时有0个点;
2坐标为0的时候可见点在三条坐标轴上一共3个;
1坐标为0的时候3*ans(ans=sigma(u(d)*(n/i)*(n/i)));
坐标都不为0的时候ans=ans=sigma(u(d)*(n/i)*(n/i)*(n/i))
提示:提交代码时不能用__int64,只能用long long
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; typedef __int64 LL;
const int maxn=;
int prime[maxn],mu[maxn],num;
bool flag[maxn]; void init()
{
int i,j;num=;mu[]=;
memset(flag,true,sizeof(flag));
for(i=;i<maxn;i++)
{
if(flag[i])
{
prime[num++]=i;mu[i]=-;
}
for(j=;j<num&&prime[j]*i<maxn;j++)
{
flag[i*prime[j]]=false;
if(i%prime[j]==)
{
mu[i*prime[j]]=;break;
}
else mu[i*prime[j]]=-mu[i];
}
}
} int main()
{
init();
int t,i,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
LL ans=;
for(i=;i<=n;i++)
ans+=(LL)mu[i]*(n/i)*(n/i)*(n/i+);
printf("%I64d\n",ans);
}
return ;
}
最新文章
- nodejs如何储存一个GBK编码的文件
- PHP扩展下载指导
- Apache 配置屏蔽某些请求头
- 创造tips的秘籍——PHP回调后门
- JDK里的设计模式
- 图算法之Floyd-Warshall 算法-- 任意两点间最小距离
- 算法总结—深度优先搜索DFS
- 划分分区GPT11
- RedHat7搭建Nginx+Apache+PHP
- eclipse频繁崩溃退出
- 十分钟让你明白Objective-C的语法(和Java、C++的对比)
- vim全局替换命令
- Apache2 三种MPM对比分析
- Java strictfp
- 不使用setCustomView,设置ActionBar标题居中
- 2017年天梯赛LV2题目汇总小结
- JProfiler的使用
- 何凯文每日一句打开||DAY8
- Python:fromkeys()方法
- SQL2008无法连接到(local),该账户当前被锁定,所以Sa用户登陆失败
热门文章
- stm32F042 (二) 按键触发中断
- SCOPE_IDENTITY和@@IDENTITY[转]
- C#:CodeSmith根据数据库中的表创建C#数据模型Model + 因为没有钱买正版,所以附加自己写的小代码
- 头文件string与string.h的区别
- php使用curl访问https返回无结果的问题
- GoF23种设计模式之行为型模式之策略模式
- OverflowError:django signed integer is greater than maximum
- centos7 安全配置
- Hive学习笔记(二)
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] C】Greedy Arkady