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;
}

 

检查站(线段树)

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;
}}

 

检查站(单调递增队列)

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