[HDU 4135&&HDU 2841&&HDU 1695]용 척 정리+수론(난이도 증가 3 단계 곡)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=4135
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2841
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1695
 
hdu 4135
제목 의 대의: a,b,n 을 입력 하 십시오.a~b 중 몇 개의 수 와 n 의 상호 소 를 구 하 라 고?1 과 어떤 수 는 서로 담백 하 다.
문제 풀이 방향:
    문 제 를 보면 우 리 는 i 가 a~b 에 속 하 는 것 을 옮 겨 다 닐 수 없다.그리고 i 가 n 과 공약수 가 있 는 지,있 으 면 서로 소 용이 없고 없 으 면 서로 소 용이 없다.시간 복잡 도 는 n^2 n 최대 100000,TLE.
    이 문 제 는 용 척 의 정 리 를 써 야 한다.
    우 리 는 먼저 이렇게 생각 할 수 있다.[1,n]중 몇 개의 수 와 m 의 상호 소 가 있 는 지,[1,n]중 몇 개의 수 와 m 의 상호 소(이 값 이 ans 라 고 가정 하면 상호 소 는 당연히 n-ans 이다.
    문 제 는 구[1,n]중 몇 개의 수 와 m 가 서로 어 울 리 지 않 는 지 로 바 뀌 었 다.
    가설 n=12,m=30
    첫 번 째 단계:먼저 m 의 인자 수(m 의 인자 수 는 2,3,5)를 구한다.
    두 번 째 단계:[1,n]에서 m 인자 의 배 수 는 당연히 서로 소화 되 지 않 는 다.
             （2,4,6,8,10,12）->n/2   6 개, （3,6,9,12）->n/3  4 개,(5,10)->n/52 개.
             급 한 게 다 겹 칠 수도 있어.서 두 르 지 마 세 요.안에 중복 되 는 것 이 있 는 지 없 는 지 우 리 는 중복 되 는 것 을 빼 야 합 니 다.
            공식 n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5).
    STEP 3:중요 한 것 이 왔 다.이 단 계 는 여러 가지 방법 이 있 습 니 다.dfs,대기 열 배열,비트 연산 이 모두 가능 합 니 다.대기 열 배열 은 dfs 보다 조금 빠 릅 니 다.여기 서 나 는 두 번 째(대기 열 배열)만 말 합 니 다.우 리 는 하나의 대기 열(배열 도 괜 찮 습 니 다)으로 나타 난 분 모 를 저장 할 수 있 습 니 다.우 리 는 대기 열의 첫 번 째 요 소 를 1 로 만 들 수 있 습 니 다.매번 나타 나 는 m 의 인자 와 대기 열 에 있 는 요 소 를 하나씩 곱 해서 대기 열 에 저장 할 수 있 습 니 다.마지막 에 저 장 된 요 소 는 바로 우리 위의 분모 입 니 다.현재 의 문 제 는 우리 가 언제 사용 하고 언제 사용 하 느 냐 가 되 었 다.여기 서 우 리 는 저장 할 때마다 하나(-1)를 더 곱 하면 우리 가 원 하 는 결 과 를 얻 을 수 있다.
 제목 은[a,b]에서 n 과 호상 소 를 요구 하 는데 우 리 는 각각[1,b]와 n 의 호상 소 와[1,a-1]과 n 의 호상 소 를 구 하 는 것 이 답 이다.
코드:
 

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 #include <vector>

 6 using namespace std;

 7 vector<int>vt;

 8 

 9 __int64  n, a, b, res;

10 __int64 que[1024];

11 

12 void fx()

13 {

14     vt.clear();

15     res=n;

16     for(int i=2; i*i<=n; i++)

17     {

18         if(res%i==0)

19         {

20           vt.push_back(i);

21           while(res%i==0)

22                res/=i;

23         }

24     }

25     if(res>1)  vt.push_back(res);

26 }

27 

28 __int64 cal(__int64 n, __int64 t)

29 {

30     int num=0;

31     que[num++]=1;

32     for(int i=0; i<vt.size(); i++)

33     {

34         int ep=vt[i];

35         int k=num;

36         for(int j=0; j<k; j++)

37             que[num++]=ep*que[j]*(-1);

38     }

39     __int64 sum=0;

40     for(int i=0; i<num; i++)

41         sum+=t/que[i];

42     return sum;

43 }

44 

45 int main()

46 {

47     int  T, tcase=0;

48     cin >> T;

49     while(T--)

50     {

51         cin >> a >> b >> n;

52         fx();

53         __int64 ans=cal(n,b)-cal(n,a-1);

54         printf("Case #%d: %I64d
",++tcase,ans);

55     }

56     return 0;

57 }

 
 
 
 hdu 2841
제목 의 대의:  N*M 의 격 점 에 나무 가 있 는데 0,0 시 에 몇 그루 의 나 무 를 볼 수 있 습 니까?
문제 풀이 방향:
그림 을 통 해 알 수 있 듯 이 A1/B1=A2/B2 는 나무 한 그루 가 보이 지 않 기 때문에 Ai/Bi 가 몇 가지 가 있 는 지 찾 아 보 는 것 이다.
A/B 에서 만약 에 A,B 가 1 보다 큰 공약수 가 있 으 면 A=A'*D B=B'*D,그러면 A/B=A'/B',즉 다른 조 의 수가 이런 것 과 같 으 면 문 제 는 몇 쌍 의 상호 질 적 인 수로 전환 되 는 지 알 수 있다.
이 문제 와 이전 문제 의 유일한 차 이 는 매 거 i 이다.1-M 에서 i 와 서로 질 적 인 수 를 찾 는 것 이다.그 중에서 1<=i<=N.
i 의 모든 소인 자 를 미리 처리 한 다음 에 용 척 구 를 하면 된다.
 
코드:
 

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 #include <vector>

 6 using namespace std;

 7 

 8 const int maxn=100001;

 9 int que[maxn];

10 vector<int>vt[maxn];

11 

12 void init()

13 {

14     for(int i=0; i<maxn; i++)

15         vt[i].clear();

16     for(int i=2; i<maxn; i++)

17     {

18         int t=i;

19         for(int j=2; j*j<=i; j++)

20         {

21             if(t%j==0)

22             {

23                 vt[i].push_back(j);

24                 while(t%j==0)

25                    t/=j;

26             }

27         }

28         if(t>1) vt[i].push_back(t);

29     }

30 }

31 

32 __int64 cal(int n, int s)

33 {

34     int num=0;

35     que[num++]=1;

36     for(int i=0; i<vt[s].size(); i++)

37     {

38         int ep=vt[s][i];

39         if(ep>n) break;

40         int k=num;

41         for(int j=0; j<k; j++)

42         {

43             que[num++]=que[j]*ep*(-1);

44         }

45     }

46     __int64 sum=0;

47     for(int i=0; i<num; i++)

48     {

49         sum+=n/que[i];

50     }

51     return sum;

52 }

53 

54 int main()

55 {

56     int T, n, m;

57     init();

58     cin >> T;

59     while(T--)

60     {

61         scanf("%d%d",&n,&m);

62         __int64 ans=n;

63         for(int i=2; i<=m; i++)

64             ans+=cal(n,i);

65         printf("%I64d
",ans);

66     }

67     return 0;

68 }

 
 
 
hdu1695
제목:a,b,c,d,k 다섯 개 드릴 게 요.x 는[a,b]y 는[c,d]에 속한다.몇 쌍(x,y)의 공약수 가 k 냐 고 물 었 다. 주의(x,y)와(y,x)는 같은 쌍 으로 간주 합 니 다.
문제 풀이 방향:
 이 문 제 는 용 반 정리+수론 소수 선별 법+수론 오로라 함 수 를 사용 했다.좋 은 문제 라 고 할 수 있다.
 제목 의 첫머리 해석 을 잘 보 세 요.a=c=1 을 가상 할 수 있 습 니 다.이것 이 있 으 면 더욱 간단 합 니 다.우 리 는 먼저 점 b,d 를 각각 k,b/=k,d/=k 로 나 눌 수 있다.
  b.d 보다 클 수 있 습 니 다.여기 서 우 리 는 d 가 b 보다 크 고 그렇지 않 으 면 교환 합 니 다.이렇게 하면[1,b],[1,d]중 몇 쌍 의 상호 소 수 를 찾 아야 합 니까?
우 리 는 i 를 1~d 에서 옮 겨 다 니 게 합 니 다.
1.i<=b 일 때 오로라 함수 로 상호 원소 의 대 수 를 직접 구 할 수 있 습 니 다.
2.i>b 일 때 용 반 정 리 를 이용 하여[1,b]에서 i 와 서로 소의 대 수 를 구한다.
여기 서 k=0 의 상황 을 주의 하 세 요.무시 하 는 것 은 바로 여기 running error time 에 몇 번 주의 하지 않 은 것 입 니 다.
이 문 제 는 용 반 정리 로 나 는 두 가지 방법,대열 배열 과 dfs 를 사용 하여 촉감 을 연습 했다.대기 열 배열 이 dfs 보다 배 빠르다.
코드:
 

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <cstring>

  5 #include <vector>

  6 using namespace std;

  7 

  8 const int maxn=100005;

  9 int que[maxn];

 10 bool color[maxn];

 11 int f[maxn], phi[maxn];

 12 vector<int>vt[maxn];

 13 

 14 void Eular()  //    

 15 {

 16     phi[1]=1;

 17     int k, num=0;

 18     memset(color,false,sizeof(color));

 19     for(int i=2; i<maxn; i++)

 20     {

 21         if(!color[i])

 22         {

 23             f[num++]=i;

 24             phi[i]=i-1;

 25         }

 26         for(int j=0; j<num&&(k=i*f[j])<maxn; j++)

 27         {

 28             color[k]=true;

 29             if(i%f[j]==0)

 30             {

 31                 phi[k]=phi[i]*f[j]; break;

 32             }

 33             else

 34                 phi[k]=phi[i]*(f[j]-1);

 35         }

 36     }

 37 }

 38 

 39 void init()   //     

 40 {

 41     for(int i=2; i<maxn; i++)

 42     {

 43         int t=i;

 44         for(int j=0; f[j]*f[j]<=i; j++)

 45         {

 46             if(t%f[j]==0)

 47             {

 48                 vt[i].push_back(f[j]);

 49                 while(t%f[j]==0)

 50                    t/=f[j];

 51             }

 52         }

 53         if(t>1) vt[i].push_back(t);

 54     }

 55 }

 56 

 57 __int64 cal(int n, int s) //          

 58 {

 59     int num=0;

 60     que[num++]=1;

 61     for(int i=0; i<vt[s].size(); i++)

 62     {

 63         int ep=vt[s][i];

 64         if(ep>n) break;

 65         int k=num;

 66         for(int j=0; j<k; j++)

 67         {

 68             que[num++]=que[j]*ep*(-1);

 69         }

 70     }

 71     __int64 sum=0;

 72     for(int i=0; i<num; i++)

 73     {

 74         sum+=n/que[i];

 75     }

 76     return sum;

 77 }

 78 

 79 /*

 80 __int64 dfs(int a, int b, int cur)  //dfs      

 81 {

 82     __int64 res=0, k;

 83     for(int i=a; i<vt[cur].size(); i++)

 84     {

 85         k=b/vt[cur][i];

 86         res+=k-dfs(i+1,k,cur);

 87     }

 88     return res;

 89 }

 90 */

 91 

 92 int main()

 93 {

 94     int  a, b, c, d, k, T, tcase=0;

 95     Eular();

 96     init();

 97     cin >> T;

 98     while(T--)

 99     {

100         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

101         if(k==0||k>b||k>d)

102         {

103             printf("Case %d: 0
",++tcase); continue;

104         }

105         b=b/k, d=d/k;

106         if(b>d) swap(b,d);

107         __int64 ans=0;

108         for(int i=1; i<=b; i++)

109         {

110             ans+=phi[i];

111         }

112         for(int i=b+1; i<=d; i++)

113         {

114             ans+=cal(b,i);

115         }

116         printf("Case %d: %I64d
",++tcase,ans);

117     }

118     return 0;

119 }