hdu1695

求两段区间中最大公约数为k的数字的对数，下界除以k后就会变成，求区间中与n互质的数字的对数。主要错在了两个地方，k=0和b，d大小的判断。
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <climits>
 7 #include <sstream>
 8 #include <fstream>
 9 #include <cstdio>
10 #include <string>
11 #include <vector>
12 #include <queue>
13 #include <cmath>
14 #include <stack>
15 #include <map>
16 #include <set>
17 
18 using namespace std;
19 typedef pair<int,int> II;
20 typedef vector<int> IV;
21 typedef vector<II> 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 "<<count++<<": 0"<<"\n";
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 "<<count++<<": "<<sum<<"\n";
85     }
86     return 0;
87 }