








FAFU 1079(帮东儿一个忙)经典素数的运用
题目大意:给你N,M,K让你求里包含多少个k的倍数,也就是满足表达式
int Count (int , int k)
{
int ans = 0;
while ( %k == 0 )
{
ans ++;
=
/ m;
}
return ans;
}
第一行一个整数t表示有t组测试数据,接下去每组三个整数n,m,k,其中 n,m,k < 109 ,t < 10000 , k > 1。
题目思路:求里有多少个K的倍数,可以转换成
里面的质因数是K的质因数的倍数的的最小值。
第一步:首先我们要枚举+筛选求出有可能成为K的质因数的 质数!在这里我们只需要枚举到并且只枚举奇数这样就大大优化了程序!
第二步:求出K的各个质因数的值和该质数出现的个数,分别存储在数组里,上限是枚举到pri[i]*pri[i]<=K;
第三步:根据已经求出的K的各个质因数和各个质因数在K里的个数,分别对每个质因数进行计算。
目的是:我们求出这个质因数在里出现的次数!然后把出现的次数ans/vt[i] ( vt[i]表示组成K的第i个质数在K里使用的次数 ) ,ans/vt[i] 也就是
里该质数出现的次数,是K里面出现次数的多少倍,也就是
里面有多少个该质数的倍数!
顺序枚举所有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 ; }} |
检查站(单调递增队列)
题意就是有两个检查站,可以从第一个检查站开进车子,也会从后面一个检查站开出车子,但是每次只能动作一次,开出或者开进,你要求查询这两个检查站之间的最重车辆。
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 | # include <iostream> # include <stdio.h> # include <list> using namespace std; struct node{ int val,id; }; int main(){ int cas,x,sn,ans,t,times,en; char c[ 10 ]; scanf( "%d" ,&cas); list <node> que; node tempt ; en=sn= 0 ; ans= 0 ; times= 0 ; while (cas--){ scanf( "%s" ,c); //这样能节约很多时间!下次进行类似的字符输入 //用来判断的时候 切记 ! if (c== 'Q' ){ if (que.empty()) printf( "0\n" ); else printf( "%d\n" ,que.front().val); } else if (c== 'I' ){ scanf( "%d" ,&x); ans++; tempt.val=x; tempt.id=ans; while (!que.empty()&&x>=que.back().val) que.pop_back(); que.push_back(tempt); } else { times++; while (!que.empty()&&que.front().id<=times) que.erase(que.begin()); } } return 0 ; } |