bzoj 2818: Gcd GCD(a,b) = 素数
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1566 Solved: 691
[Submit][Status]
Description
给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
Sample Output
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std; typedef long long LL;
const int maxn = 1e7+;
bool s[maxn];
int prime[maxn],len = ;
int mu[maxn];
int g[maxn];
int sum1[maxn];
void init()
{
memset(s,true,sizeof(s));
mu[] = ;
for(int i=; i<maxn; i++)
{
if(s[i] == true)
{
prime[++len] = i;
mu[i] = -;
g[i] = ;
}
for(int j=; j<=len && (long long)prime[j]*i<maxn; j++)
{
s[i*prime[j]] = false;
if(i%prime[j]!=)
{
mu[i*prime[j]] = -mu[i];
g[i*prime[j]] = mu[i] - g[i];
}
else
{
mu[i*prime[j]] = ;
g[i*prime[j]] = mu[i];
break;
}
}
}
for(int i=; i<maxn; i++)
sum1[i] = sum1[i-]+g[i];
} int main()
{
int a;
init();
while(scanf("%d",&a)>)
{
LL sum = ;
for(int i=,la = ; i<=a; i = la+)
{
la = a/(a/i);
sum = sum + (long long)(sum1[la] - sum1[i-])*(a/i)*(a/i);
}
printf("%lld\n",sum);
}
return ;
}
spoj
4491. Primes in GCD TableProblem code: PGCD |
Johnny has created a table which encodes the results of some operation -- a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height a and width b), indexed from (1,1) to (a,b), and with the value of field (i,j) equal to gcd(i,j). He wants to know how many times he has used prime numbers when writing the table.
Input
First, t ≤ 10, the number of test cases. Each test case consists of two integers, 1 ≤ a,b < 107.
Output
For each test case write one number - the number of prime numbers Johnny wrote in that test case.
Example
Input:
2
10 10
100 100
Output:
30
2791 一样的题,只不过 GCD(x,y) = 素数 . 1<=x<=a ; 1<=y<=b;
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std; typedef long long LL;
const int maxn = 1e7+;
bool s[maxn];
int prime[maxn],len = ;
int mu[maxn];
int g[maxn];
int sum1[maxn];
void init()
{
memset(s,true,sizeof(s));
mu[] = ;
for(int i=;i<maxn;i++)
{
if(s[i] == true)
{
prime[++len] = i;
mu[i] = -;
g[i] = ;
}
for(int j=;j<=len && (long long)prime[j]*i<maxn;j++)
{
s[i*prime[j]] = false;
if(i%prime[j]!=)
{
mu[i*prime[j]] = -mu[i];
g[i*prime[j]] = mu[i] - g[i];
}
else
{
mu[i*prime[j]] = ;
g[i*prime[j]] = mu[i];
break;
}
}
}
for(int i=;i<maxn;i++)
sum1[i] = sum1[i-]+g[i];
} int main()
{
int T,a,b;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&a,&b);
if(a>b) swap(a,b);
LL sum = ;
for(int i=,la = ;i<=a;i = la+)
{
la = min(a/(a/i),b/(b/i));
sum = sum + (long long)(sum1[la] - sum1[i-])*(a/i)*(b/i);
}
printf("%lld\n",sum);
}
return ;
}
最新文章
- 2016 - 1- 22 img tag and the lists (intro to HMTL&;CSS)
- 取消本地SVN文件夹与服务器关联
- ApacheBench(ab)使用简介
- Thinkphp与Ucenter整合笔记
- 用caffe给图像的混乱程度打分
- 基于脚本的modelsim自动化仿真笔记
- 最短路之Bellman-Ford算法
- [http服务]
- 《java入门第一季》之Random类和获取随机数案例
- 重装Windows后修复Linux引导
- java 从指定行读文件,执行系统命令
- iOS:UIButton扩大按钮的响应区域
- 开源中文分词工具探析(七):LTP
- Java 中数据库连接池的比较
- selenium学习一
- http406错误
- http协议/获得请求/中文参数处理/访问数据库
- HTML基本格式
- Mali GPU OpenGL ES 应用性能优化--測试+定位+优化流程
- 文件上传—SSM框架文件上传