UVA10791 Minimum Sum LCM 数论素因子 - c++编程基础

题目意思是给你一个数N，并且限定N是两个数 a,b,的最小公倍数，求使得 a+b 最小，并求出 a+b

分析：当N为素数时，那么 a+b 最小肯定就是 N+1了，因为素数除了1和本身外无其它因子了

还有就是题目给的N的范围是 N<=2^31 -1,注意2^31 -1是素数，所以答案应为 N+1，可是此时的N+1已经超了 int的范围内，需要注意
接下来就是一般情况下的了，设pi为素数序列，那么任何一个数 N都可以写成 N=(p1^m1)*(p2^m2)*(p3^m3)……,那么本题最小和其实就是(p1^m1)+(p2^m2)+(p3^m3)……，题目做多了就知道了，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // const int MAXN=(1<<31)-1; bool isprime[50000+5]; int prime[50000+5]; int quick(int a,int b) { int ans=1; while(b) { if(b&1) { ans*=a; b--; } b>>=1; a*=a; } return ans; } void init()//依据题目数据范围处理一定范围内的素数 { memset(isprime,false,sizeof(isprime)); for(int i=2;i<50005;i++) if(!isprime[i]) for(int j=i*2;j<50005;j+=i) isprime[j]=true; int k=0; for(int i=2;i<50005;i++) if(!isprime[i]) prime[k++]=i; } int main() { init(); int Case=0; int n; while(scanf("%d",&n),n) { printf("Case %d: ",++Case); if(n == MAXN)//题目范围内最大的那个是素数，特判掉 { printf("%lld\n",(ll)n+1); continue; } int mid=int(sqrt(n*1.0)); int tmp=n; int num=0; int cnt=0; int mark=0; int ans=0; while(tmp>1) { bool flag=false; num=0; if(prime[cnt] > mid)break; while(tmp%prime[cnt] == 0) { tmp/=prime[cnt]; num++; flag=true; } if(flag) mark++; if(num) ans+=quick(prime[cnt],num); cnt++; } if(mark == 1 && tmp == 1) ans=n+1; else if(ans == 0) ans=n+1; else if(tmp > 1) ans+=tmp; printf("%d\n",ans); } return EXIT_SUCCESS; }