程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> RGCDQ(線段樹+數論)

RGCDQ(線段樹+數論)

編輯:C++入門知識

RGCDQ(線段樹+數論)


題意:求n和m之間的所有數的素因子個數的最大gcd值。

分析:這題好惡心,看著就是一顆線段樹,但本題有一定的規律,我也是後來才發現,我還沒推出這個規律,就不說了,就用純線段樹解答吧。因為個點數都小於1000000所以素因子個數不會超過7個所以建一個線段樹,最下面一層是每個節點的素因子個數為1,2,3,4,5,6,7的有多少個,父節點求和,最終查詢的是n到m之間有多少個1,2,3,4,5,6,7然後存在就求一下gcd著最大就好了

本題最重要的時間和空間,顯然線段數中的點不會很大,所以采用short類型

代碼如下:

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
int gcd(int a,int b){
    return (b==0)?a:gcd(b,a%b);
}
const int N=100000;
int prime[N]={0};
int num_prime=0;
bool isNotPrime[N]={1,1};
void su1(){
    for(long i = 2 ; i < N ; i ++){
        if(!isNotPrime[i])
        prime[num_prime++]=i;
        for(long j = 0 ; j < num_prime &&i*prime[j]>1;
    if(id<=i)updat(id,j,l,i,2*mid);
    else updat(id,j,i+1,r,2*mid+1);
    a[mid][j]=a[2*mid][j]+a[2*mid+1][j];
}
int sum[8];
void su(int l,int r,int mid,int ll,int rr){
    if(l>=ll&&r<=rr){
        for(int i=1;i<=7;i++)
        sum[i]+=a[mid][i];
        return;
    }
    int i=(l+r)>>1;
    if(ll<=i)su(l,i,2*mid,ll,rr);
    if(rr>i)su(i+1,r,2*mid+1,ll,rr);
}//建樹,求和,這是重點
int main(){
    memset(a,0,sizeof(a));
    su1();
//    for(int i=1;i<=100;i++){
//    if(isNotPrime[i])
//    cout<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved