FAFU 1079（帮东儿一个忙）经典素数的运用

题目大意：给你N，M，K让你求$$C_n^m$$里包含多少个k的倍数，也就是满足表达式

int Count (int $$C_n^m$$, int k)
  {
   int ans = 0;
   while ( $$C_n^m$$%k == 0 )
   {
    ans ++;
    $$C_n^m$$ = $$C_n^m$$ / m;
   }
   return ans;
  }

 第一行一个整数t表示有t组测试数据，接下去每组三个整数n，m，k，其中 n，m，k < 109 ,t < 10000 , k > 1。

题目思路：求$$C_n^m$$里有多少个K的倍数，可以转换成$$C_n^m$$里面的质因数是K的质因数的倍数的的最小值。

第一步：首先我们要枚举+筛选求出有可能成为K的质因数的 质数！在这里我们只需要枚举到$$\sqrt(K)$$并且只枚举奇数这样就大大优化了程序！

第二步：求出K的各个质因数的值和该质数出现的个数，分别存储在数组里，上限是枚举到pri[i]*pri[i]<=K;

第三步：根据已经求出的K的各个质因数和各个质因数在K里的个数，分别对每个质因数进行计算。

             目的是：我们求出这个质因数在$$C_n^m$$里出现的次数！然后把出现的次数ans/vt[i]   ( vt[i]表示组成K的第i个质数在K里使用的次数 ) ，ans/vt[i]  也就是 $$C_n^m$$里该质数出现的次数，是K里面出现次数的多少倍，也就是$$C_n^m$$里面有多少个该质数的倍数！

顺序枚举所有K的质因数，取ans/vt[i]最小的！

源程序+部分注释：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int N=100000;
int pri[100000];
bool flag[100000];
int getprime(){
    int t=0,i,j,times;
    pri[++t]=2;
    for(i=1;i<=N;i++)
        flag[i]=1;
      //枚举到到N，也就是题目给出的最大值的开2次方！
    for(i=3;i<=N;i+=2){//只枚举奇数！
        if(flag[i]==1){
            pri[++t]=i;
                     //筛选求素数：
            for(j=i;j<=N;j+=i)
                flag[j]=0;
        }
    }
    return 0;
}
 
int des(int k,int* vs,int* vt){
    int t=0,i,times;
    for(i=1;pri[i]*pri[i]<=k;i++){
        times=0;
        while(k%pri[i]==0){
            times++;
            k/=pri[i];
        }
        if(times>0){
            vt[++t]=times;
            vs[t]=pri[i];  
        }
    }
    if(k!=1){
        vs[++t]=k;
        vt[t]=1;   
    }
    return t;
}
 
int add(int n,int t){
    int ans=0;
    while(n>=t){
        ans+=n/=t;
     //首先是能被t整除的，然后把n
    //附为n对t的倍数，也就是继续求
    //他的倍数的值里面还有多少个t的倍数！
    }
    return ans;
}
 
int cpt(int n,int m,int t,int ct){
    int tp=0;
    tp+=add(n,t);
    tp-=add(n-m,t);
    tp-=add(m,t);
    return tp/ct;
}
 
int main(){
    int cas,m,n,i,k;
    int Min=-1,ans,vs[100],vt[100];
    scanf("%d",&cas);
    getprime();
    while(cas--){
        scanf("%d %d %d",&n,&m,&k);
        Min=-1;
        int times=des(k,vs,vt);
        for(i=1;i<=times;i++){
            ans=cpt(n,m,vs[i],vt[i]);
            if(Min==-1||ans<Min)
                Min=ans;
        }
        printf("%d\n",Min);
    }
    return 0;
}

 

农大月赛解题报告 Comments(0) 2011年4月12日 21:03

检查站（线段树）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<stdio.h>
using namespace std;
 
struct node{
    int r,l,Max;
}s[1000400];
 
void Build(int x,int y,int num){
    s[num].l=x;
    s[num].r=y;
    s[num].Max=0;
    if(x==y)
        return;
    int mid=(x+y)>>1;
    Build(x,mid,num+num);
    Build(mid+1,y,num+num+1);
}
int modify(int pos,int count,int num){
    if(s[num].l==s[num].r&&s[num].l==pos){
        s[num].Max=count;
    }
    else{
        int mid=(s[num].l+s[num].r)/2;
        if(pos<=mid)
            modify(pos,count,num+num);
        else
            modify(pos,count,num+num+1);
        s[num].Max=max(s[num+num].Max,s[num+num+1].Max);
    }
}
 
int main(){
    int cas,i,x;
    int times=1;
    char ch[10];
    scanf("%d",&cas);
    int sn=1;
    int tn=1;
    Build(1,100000,1);
    while(cas--){
        scanf("%s",ch);
        if(ch[0]=='I'){
            scanf("%d",&x);
            modify(tn,x,1);
            tn++;
        }
        else if(ch[0]=='Q'){
            int ans=s[1].Max;
            printf("%d\n",ans);
        }
        else{
            modify(sn,0,1);
            sn++;
        }
    }
    return 0;
#include<iostream>
#include<stdio.h>
using namespace std;
 
struct node{
    int r,l,Max;
}s[1000400];
 
void Build(int x,int y,int num){
    s[num].l=x;
    s[num].r=y;
    s[num].Max=0;
    if(x==y)
        return;
    int mid=(x+y)>>1;
    Build(x,mid,num+num);
    Build(mid+1,y,num+num+1);
}
int modify(int pos,int count,int num){
    if(s[num].l==s[num].r&&s[num].l==pos){
        s[num].Max=count;
    }
    else{
        int mid=(s[num].l+s[num].r)/2;
        if(pos<=mid)
            modify(pos,count,num+num);
        else
            modify(pos,count,num+num+1);
        s[num].Max=max(s[num+num].Max,s[num+num+1].Max);
    }
}
 
int main(){
    int cas,i,x;
    int times=1;
    char ch[10];
    scanf("%d",&cas);
    int sn=1;
    int tn=1;
    Build(1,100000,1);
    while(cas--){
        scanf("%s",ch);
        if(ch[0]=='I'){
            scanf("%d",&x);
            modify(tn,x,1);
            tn++;
        }
        else if(ch[0]=='Q'){
            int ans=s[1].Max;
            printf("%d\n",ans);
        }
        else{
            modify(sn,0,1);
            sn++;
        }
    }
    return 0;
}}

 

农大月赛解题报告 Comments(0) 2011年4月12日 14:49

检查站（单调递增队列）

题意就是有两个检查站，可以从第一个检查站开进车子，也会从后面一个检查站开出车子，但是每次只能动作一次，开出或者开进，你要求查询这两个检查站之间的最重车辆。

 

农大月赛解题报告 Comments(0) 2011年4月09日 17:05







Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.