撰写- 题意：两个整数a, b。求出a, a – 1, a – 2……..b +1这些整数能被拆分成多少个素数相乘，把每个的拆分结果相加起来。例如 a = 6, b = 3. 那么结果= 2(4=2*2) + 1(5=5) + 2(6=2*3) = 5
- 题解：素数筛法，先把每个数能拆分成多少个素数预处理一下，之后用前缀和的思想，相减一下就行了
- 然而有些人想用阶乘分解公式，但是阶乘分解公式不能够预处理…
- 错解
-
//#include<bits/stdc++.h> #include<algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='?'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='?')?-1:1; ret=(c=='?')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn=5e6+10; int vis[maxn]; int P[maxn]; int cnt; void init(int n) { vis[1]=1; cnt=0; rep(i,1,n) { if(!vis[i]) { P[++cnt]=i; for(int j=i*2; j<=n; j+=i) { if(!vis[j])vis[j]=1; } } } } int main() { ios::sync_with_stdio( false ); int t; cin>>t; init(5000000); while(t--) { int a,b; cin>>a>>b; ll ans=0; rep(i,1,cnt){ ll base=P[i]; if(base>a)break; ll num=base; while(num<=a){ ans+=a/num; if(num<=b)ans-=b/num; num*=base; } } cout<<ans<<endl; } return 0; }
-
- 正解
-
//#include<bits/stdc++.h> #include<algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='?'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='?')?-1:1; ret=(c=='?')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn=5e6+10; bool is_prime[maxn]; int num[maxn]; void fac(){ CLR(num); CLR(is_prime); rep(i,2,maxn-10){ if(!is_prime[i]){ for(int j=i;j<=maxn-10;j+=i){ int tmp=j; while(tmp%i==0){ num[j]++; tmp/=i; } if(j!=i)is_prime[j]=1; } } } rep(i,2,maxn-10){ num[i]=num[i]+num[i-1]; } } //即使不输入到缓存区，cincout还是TLE int main(){ //ios::sync_with_stdio( false ); fac(); int t,a,b; //cin>>t; scan_d(t); while(t--){ scan_d(a); scan_d(b); //cin>>a>>b; //cout<<num[a]-num[b]<<"\n"; outt(num[a]-num[b]); printf("\n"); } return 0; }
-
