首页 > hdu1695

hdu1695

求两段区间中最大公约数为k的数字的对数，下界除以k后就会变成，求区间中与n互质的数字的对数。主要错在了两个地方，k=0和b，d大小的判断。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <string>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include <set>
17 
18 using namespace std;
19 typedef pair<int,int> II;
20 typedef vector<int> IV;
21 typedef vector IIV;
22 typedef vector<bool> BV;
23 typedef long long i64;
24 typedef unsigned long long u64;
25 typedef unsigned int u32;
26 #define For(t,v,c) for(t::const_iterator v=c.begin(); v!=c.end(); ++v)
27 #define IsComp(n) (_c[n>>6]&(1<<((n>>1)&31)))
28 #define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))
29 const int MAXP = 46341;
30 const int SQRP = 216;
31 int _c[(MAXP>>6)+1];
32 IV primes;
33 void prime_sieve() {
34     for ( int i = 3; i <= SQRP; i += 2 )
35         if ( !IsComp(i) ) for ( int j = i*i; j <= MAXP; j+=i+i ) SetComp(j);
36     primes.push_back ( 2 );
37     for ( int i = 3; i <= MAXP; i += 2 ) if ( !IsComp(i) ) primes.push_back ( i );
38 }
39 void prime_factorize ( int n, IIV &f ) {
40     int sn =(int) sqrt ( (double)n );
41     For ( IV, it, primes ) {
42         int prime = *it;
43         if ( prime > sn ) break; if ( n % prime ) continue;
44         int e = 0; for ( ; n%prime == 0; e++, n/= prime );
45         f.push_back ( II(prime,e) );
46         int sn = (int)sqrt( (double)n);
47     }
48     if ( n > 1 ) f.push_back( II(n,1) );
49 }
50 IIV aa;
51 u64 dfs ( int cur, int val ) {
52     u64 res = 0;
53     for ( int i = cur; i < aa.size(); ++i ) {
54         res += val/aa[i].first- dfs( i+1,val/aa[i].first );
55     }
56     return res;
57 }
58 u64 fun ( int val, int m ) {
59     aa.clear ( );
60     prime_factorize ( m, aa );
61     return val - dfs(0,val);
62 }
63 int main()
64 {
65     prime_sieve ( );
66     int a,b,c,d,n,sum,i,j,count=1,tmp,t;
67     cin>>t;
68     while(t--)
69     {
70         cin>>a>>b>>c>>d>>n;
71         if(n==0)
72         {
73             cout<<"Case "<": 0"<<"
";
74             continue;
75         }
76         if(b>d)
77         {
78             tmp=b;b=d;d=tmp;
79         }
80         b/=n;d/=n;
81         sum=0;
82         for(i=c;i<=d;i++)
83         sum+=fun(min(i,b),i);
84         cout<<"Case "<": "<"
";
85     }
86     return 0;
87 }

 

转载于:https://www.cnblogs.com/Acgsws/archive/2013/06/11/3131765.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • 欧拉筛

    欧拉筛又称线性筛，可以在线性的时间内筛出素数，因此在时间上要优于埃拉托斯特尼筛法。 欧拉筛是怎么做到在线性的时间内筛素数呢？先看代码。 1 int n,vis[maxn],prime[maxn],cnt; 2 for(int i=2;i<=n;++i) { 3 if(!vis[i]) prime[++cnt]...

©2024 11GX.COM