主頁 > 後端開發 > UVA11610 【Reverse Prime】

UVA11610 【Reverse Prime】

2020-09-10 00:57:36 後端開發

本人看到此題沒有翻譯,就附帶了一個自己的翻譯版本


思考

這一題,它的第一個要求是找出所有 \(7\) 位反向質數及其質因數的個數,

我們應該需要質數篩篩選1~\(10^{7}\)的所有數,這里就不慢慢介紹了,但是,重讀題,我們突然發現反向質數都是 \(7\) 位,而將它反過來后的數字卻是 \(6\) 位數,這就說明了最后一位數肯定是0,這樣,我們就可以只篩到\(10^{6}\),也就是說,篩所有反向數,如果是質數,反向過來,末尾填 \(0\) 就是了,這樣,我們就減少了時間復雜度,這一部分函式的代碼如下:

#define N 1e6+10
void Euler_prime()   //歐拉篩
{

	memset(is_prime,true,sizeof(is_prime));   //先全部標記為是質數  
	is_prime[1]=false;	//特判一下1不是質數
	for(int i=2;i<N;i++)	//列舉2~N的每個數
	{
		if(is_prime[i]) prime[++tot]=i;	//如果是質數
		for(int j=1;j<=tot;j++)	
		{
			if(prime[j]*i>N)
				break;
			is_prime[prime[j]*i]=false;
			if(i%prime[j]==0)   
				break;
		}
	}
}
int solve(int num)  //實作了num數的反向
{
    int len=0,ret=0,bit[20];
    while(num)  
    {
        bit[len++]=num%10;
        num/=10;
    }
    for(int i=0;i<len;i++)
    {
        ret=ret*10+bit[i];
    }       //本函式到這里實作了res=num的反向數
    while(ret<100000) ret*=10;  //因為求出來的數不一定是6位數,所以要加上這行代碼,末尾填0
    return ret;
}

這里求完了,接著就要算出它的質因數的個數,這個應該是非常簡單的了,但是還要注意,因為我們是篩選的1~\(10^{6}\)的質數,再反過來在末尾填 \(0\) 的,順序都被打亂了,所以我們要將所有反向質數從小到大排序,這里為了離散化,使用了 \(STL\) 庫中的 \(map\),不懂的同學可以自行百度一下,初始化的部分如下:

map<int,int>m;  //為了能夠離散化,我使用了map
void init() //初始化函式
{
    Euler_prime();   //先篩了吧……
    for(int i=1;i<=tot;i++)
        a[i]=solve(prime[i]);   //a[i]表示第prime[i]個數的反向質數
    sort(a+1,a+1+tot);  //此題需要從小到大排序,才能在后面的二分中查詢
    for(int i=1;i<=tot;i++)
        m[a[i]]=i;  //將其離散化
/*以下函式部分實作了求i的質因數*/
    for(int i=1;i<=tot;i++) 
    {
        fac[i]=2;	//fac[i]用來貯存第i個反向質數的質因數的數量,初值一定要賦2
        int tmp=a[i];
        for(int j=1;j<=tot&&prime[j]*prime[j]<=tmp;j++) 
        {
            while(tmp%prime[j]==0)
            {
                tmp/=prime[j];
                fac[i]++;
            }
        }
        if(tmp>1) fac[i]++; //在特殊情況下,tmp未除盡,質因數的數量要再加一個
    }
}

現在,再來看看題目給我們的 \(2\) 個操作,一個是洗掉,一個是查詢,如果我們用普通的模擬來解決的話,肯定是會超時的,這里,我們就會想到一種特殊的資料結構——樹狀陣列,也就是此題的關鍵,由于題目的特殊性,這里,我們必須要定義兩個樹狀陣列,一個樹狀陣列 \(c1\) 記錄當前 \(i\) 節點之前有多少個數,而另一個 \(c2\) 記錄了從第一個位置到當前位置反向質數的質因數的個數的總和,在查詢時,我們還要注意一下,要找出第 \(0\)\(i\) 的所有的反向質數的質因數的數量的累計總和,我們需要找出它的位置,因此可以用二分來解決這個問題,這時,問題就變得很簡單,

樹狀陣列的代碼如下:

/**********以下是樹狀陣列基本函式**********/
int lowbit(int k)   //神奇的lowbit函式
{
    return k&-k;
}
void add1(int x,int v)  //
{
    for(int i=x;i<N;i+=lowbit(i))
        c1[i]+=v;
}
void add2(int x,int v)  //
{
    for(int i=x;i<N;i+=lowbit(i))
        c2[i]+=v;
}
ll getsum1(int x)   //
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=c1[i];
    return ans;
}
ll getsum2(int x)   //
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))   
        ans+=c2[i];
    return ans;
}
/**********以上是樹狀陣列基本函式**********/
int main()
{
    init(); //初始化......
	char op[2]; //因為一個字符的輸入總是有問題,所以就定義字串啦
    int k;
    for(int i=1;i<=tot;i++)
    {
        add1(i,1);  //存在則壓入數字1
        add2(i,fac[i]); //當前位置有多少個反向質數
    }
    while(scanf("%s%d",op,&k)!=EOF) //輸入
    {
        if(op[0]=='q')  //既然要輸出0~i的所有反向質數,那么我們需要將它先在樹狀陣列中找出來,才好輸出總和
        {
            k++;    //因為本人習慣于從1開始,而此題從0開始,只得k++
            int l=1,r=tot,mid;  //既然我們要將這個數在樹狀陣列中找出,那么我們用二分是個不錯的選擇!
            while(l<=r)
            {
                mid=(l+r)/2;    //用mid變數來搜出k的位置
                ll tmp=getsum1(mid);        //記錄一下mid的位置
                if(tmp==k)  //搜出來了就break
                    break;
                else if(tmp<k)  //如果當前的比k小,說明當前數左邊的數也肯定也比k小,所以往右找
                    l=mid+1;
                else    //否則如果當前的比k大,說明當前數右邊的數也肯定也比k大,所以往左找
                    r=mid-1;
            }
            printf("%lld\n",getsum2(mid));  //最后輸出總和就好啦!
        }
        if(op[0]=='d')  
        {
            add1(m[k/10],-1);   //不存在了就減去1,(就是把它刪了)
            add2(m[k/10],-fac[m[k/10]]);    //將這個數從第一個位置到當前位置有多少個反向質數表為0(也是把它刪了^_^)刪數時因為轉換的是6位數,所以要這里要/10
        }
    }
	return 0;
}

呼——整篇文章就差不多了,我再把完整代碼整合一下:

#include <bits/stdc++.h>
#define N 1000001   //宏定義一個最大值
#define ll long long    //宏定義ll為long long (懶~)
using namespace std;    //命名空間
bool is_prime[N];   //is_prime[i]表示的是i是否為質數,true則是,false則不是
int prime[N],tot=0,a[N],fac[N];  //prime存貯質數,tot存盤質數有多少,a[i]記錄了prime[i]的反向質數,fac[i]存盤的是i的質因數的個數
ll c1[N],c2[N]; //這里要定義兩個樹狀陣列,一個樹狀陣列c1記錄當前i節點之前有多少個數,而另一個c2記錄了從第一個位置到當前位置反向質數的質因數的個數的總和
map<int,int>m;  //為了能夠離散化,我使用了map
void Euler_prime()   //歐拉篩
{

	memset(is_prime,true,sizeof(is_prime));     
	is_prime[1]=false;
	for(int i=2;i<N;i++)
	{
		if(is_prime[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++)
		{
			if(prime[j]*i>N)
				break;
			is_prime[prime[j]*i]=false;
			if(i%prime[j]==0)   
				break;
		}
	}
}
int solve(int num)  //實作了num數的反向
{
    int len=0,ret=0,bit[20];
    while(num)  
    {
        bit[len++]=num%10;
        num/=10;
    }
    for(int i=0;i<len;i++)
    {
        ret=ret*10+bit[i];
    }       //本函式到這里實作了res=num的反向數
    while(ret<100000) ret*=10;  //因為求出來的數不一定是6位數,所以要加上這行代碼
    return ret;
}
void init() //初始化函式
{
    Euler_prime();   //先篩了吧……
    for(int i=1;i<=tot;i++)
        a[i]=solve(prime[i]);   //a[i]表示第prime[i]個數的反向質數
    sort(a+1,a+1+tot);  //此題需要排序
    for(int i=1;i<=tot;i++)
        m[a[i]]=i;  //將其離散化
/*以下函式部分實作了求i的質因數*/
    for(int i=1;i<=tot;i++) 
    {
        fac[i]=2;
        int tmp=a[i];
        for(int j=1;j<=tot&&prime[j]*prime[j]<=tmp;j++) 
        {
            while(tmp%prime[j]==0)
            {
                tmp/=prime[j];
                fac[i]++;
            }
        }
        if(tmp>1) fac[i]++; //在特殊情況下,要加一個
    }
}
/**********以下是樹狀陣列基本函式**********/
int lowbit(int k)   //神奇的lowbit函式
{
    return k&-k;
}
void add1(int x,int v)  //
{
    for(int i=x;i<N;i+=lowbit(i))
        c1[i]+=v;
}
void add2(int x,int v)  //
{
    for(int i=x;i<N;i+=lowbit(i))
        c2[i]+=v;
}
ll getsum1(int x)   //
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=c1[i];
    return ans;
}
ll getsum2(int x)   //
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))   
        ans+=c2[i];
    return ans;
}
/**********以上是樹狀陣列基本函式**********/
int main()
{
    init(); //初始化......
	char op[2]; //因為一個字符的輸入總是有問題,所以就定義字串啦
    int k;
    for(int i=1;i<=tot;i++)
    {
        add1(i,1);  //存在則壓入數字1
        add2(i,fac[i]); //當前位置有多少個反向質數
    }
    while(scanf("%s%d",op,&k)!=EOF) //輸入
    {
        if(op[0]=='q')  //既然要輸出0~i的所有反向質數,那么我們需要將它先在樹狀陣列中找出來,才好輸出總和
        {
            k++;    //因為本人習慣于從1開始,而此題從0開始,只得k++
            int l=1,r=tot,mid;  //既然我們要將這個數在樹狀陣列中找出,那么我們用二分是個不錯的選擇!
            while(l<=r)
            {
                mid=(l+r)/2;    //用mid變數來搜出k的位置
                ll tmp=getsum1(mid);        //記錄一下mid的位置
                if(tmp==k)  //搜出來了就break
                    break;
                else if(tmp<k)  //如果當前的比k小,說明當前數左邊的數也肯定也比k小,所以往右找
                    l=mid+1;
                else    //否則如果當前的比k大,說明當前數右邊的數也肯定也比k大,所以往左找
                    r=mid-1;
            }
            printf("%lld\n",getsum2(mid));  //最后輸出總和就好啦!
        }
        if(op[0]=='d')  
        {
            add1(m[k/10],-1);   //不存在了就減去1,(就是把它刪了)
            add2(m[k/10],-fac[m[k/10]]);    //將這個數從第一個位置到當前位置有多少個反向質數表為0(也是把它刪了^_^)刪數時因為轉換的是6位數,所以要這里要/10
        }
    }
	return 0;
}
/*
    這么長的代碼終于打完了,呼——
    來總結一下:
    - 看到質數,數量眾多,首先想質數篩(推薦歐拉篩)
    - 在資料一對一映射時,為了省時間省財富,我推薦STL的map
    - 做題時,要找出樹狀陣列的基本模型,判斷樹狀陣列維護什么,需要幾個維護
    - 在查找時,要學會使用二分,事半功倍
    (其實主要還是樹狀陣列,只不過加了一個質數篩,二分和一些操作而已)
*/

轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/250.html

標籤:C++

上一篇:Codeforces 1400E Clear the Multiset(貪心 + 分治)

下一篇:統計區間素數數量

標籤雲
其他(123570) Java(13369) Python(12729) C(7542) 區塊鏈(7372) JavaScript(7048) 基礎類(6313) AI(6244) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4120) MySQL(4012) Linux(3394) C語言(3288) C++語言(3117) Java相關(2746) 疑難問題(2699) 單片機工控(2479) Web開發(1951) 網絡通信(1793) 數據庫相關(1767) VB基礎類(1755) PHP(1727) 開發(1646) 系統維護與使用區(1617) .NETCore(1586) 基礎和管理(1579) JavaEE(1566) C++(1527) 專題技術討論區(1515) Windows客戶端使用(1484) HtmlCss(1466) ASP.NET(1428) Unity3D(1354) VCL組件開發及應用(1353) HTML(CSS)(1220) 其他技術討論專區(1200) WindowsServer(1192) .NET技术(1165) 交換及路由技術(1149) 語言基礎算法系統設計(1133) WindowsSDKAPI(1124) 界面(1088) JavaSE(1075) Qt(1074) VBA(1048) 新手樂園(1016) 其他開發語言(947) Go(907) HTML5(901) 新技術前沿(898) 硬件設計(872) 區塊鏈技術(860) 網絡編程(857) 非技術版(846) 一般軟件使用(839) 網絡協議與配置(835) Eclipse(790) Spark(750) 下載資源懸賞專區(743)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態,例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1:當函式不可能拋出例外或不能接受拋出例外時,使用noexcept 理由 如果不打算拋出例外的話,程式就會認為無法處理這種錯誤,并且應當盡早終止,如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接:https://codeforces.com/problemset/problem/1400/E 來源:Codeforces 思路:給你一個陣列,現在你可以進行兩種操作,操作1:將一段沒有 0 的區間進行減一的操作,操作2:將 i 位置上的元素歸零。最終問:將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯,就附帶了一個自己的翻譯版本 思考 這一題,它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數,這里就不慢慢介紹了。但是,重讀題,我們突然發現反向質數都是 $7$ 位,而將它反過來后的數字卻是 $6$ 位數,這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記:C++中的 const 變數詳解,教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中,會分配記憶體(也就是說可以通過地址間接修改變數的值)。測驗代碼如下: 運行結果: 2、全域const變數存放在只讀資料段(不能通過地址修改,會發生寫入錯誤), 默認為外部聯編,可以給其他源檔案使用(需要用extern關鍵字修飾) 運行結果: ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中,添加資源 2. 點擊新添加的資源,復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案,編輯,使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索,點擊查找全部,然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h,在其中預先定義好宏 ID(不清楚其實ID值應該設定多少,可以先新建一個相同的資源項,再在這個資源的ID值的基礎上遞增即可) 2. 在資源視圖中選中專案資源,按F7編輯資源檔案,按 ID 型別 相對路徑的形式添加 資源。(別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記:關于C++的參考型別,專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考,也叫別名。 參考就是給一個變數名取一個變數名,方便我們間接地使用這個變數。我們可以給一個變數創建N個參考,這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間,占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名,但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++:初學者完整指南

    眾所周知,C ++的學習曲線陡峭,但是花時間學習這種語言將為您的職業帶來奇跡,并使您與其他開發人員區分開。您會更輕松地學習新語言,形成真正的解決問題的技能,并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣(即清晰一致的編碼風格,在撰寫代碼時注釋代碼,并限制類內部的可見性),并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • 在C#中,如何為Praxedo業務事件附件管理器創建SOAP集成?

    我們使用 Praxedo,需要將其與我們的其他解決方案集成。他們的 API 需要使用 SOAP,而且還需要 MTOM 和基本身份驗證。我們已經成功地與多種服務集成,例如他們的客戶經理。在客戶...

    uj5u.com 2021-10-16 15:47:18 more
  • Weblogic14c-webservice-description-name在weblogic-webservice

    我使用以下注釋將我的無狀態 ejb 公開為 Web 服務:@WebService( name = "MyServicePort", portName = "MyServicePort", serviceName = "MyService",)@SOAPBinding(...

    uj5u.com 2021-10-16 15:45:15 more
  • 如何在docker環境中安裝yarn?

    現在,我正在嘗試在 docker 上為 Ruby on rails 創建環境。我閱讀了一些人撰寫并嘗試過的檔案和一些博客。但是我遇到了錯誤并且無法完成。好像我必須在docker環境中安裝yarn,...

    uj5u.com 2021-10-16 15:40:43 more
  • 如何查詢按日期過濾的活動記錄?

    如何從我的資料庫中選擇僅在 5 月份處于活動狀態的所有學生學生?我在活動記錄檔案中找不到它。我只設法查詢了 5 月份創建的學生,而不是所有學生都激活了....Student.where(st...

    uj5u.com 2021-10-16 15:39:52 more
  • 選擇一個Gradle任務,以便每次運行測驗

    當我第一次運行測驗(方法)時,我有這個選單
    但是如果我從當前選單再次運行這個測驗(第二次或更多次),它將運行我最近運行的任務。所以我需要幫助,如何配置IntelliJ Idea,使IDEA總是...

    uj5u.com 2021-10-16 15:29:58 more
  • cypress上的invoke()方法如果呼叫兩次就不作業了

    我是Cypress的新手,我想用一個已經存在的網頁來實作一些簡單的測驗。我對結果有點困惑,因為我呼叫了兩次invoke():第一次是檢查初始值(0%),第二次是設定一個新的值并檢查變化,但是...

    uj5u.com 2021-10-16 15:28:48 more
  • 用jest和testing-library測驗組件內的一個函式

    我是testing-library和jest的新手,我想測驗組件內部的一個函式,它能改變一個輸入的值。這個組件是一個表單,它的另一個組件是一個輸入。
    export const Form=() => {
    const [n...

    uj5u.com 2021-10-16 15:28:44 more
  • TypeScript通用型將所有的特定型別改為另一種型別

    我試圖想出一種型別,即接受一個物件并將所有型別為number的鍵設定為string。 下面的方法不起作用:...

    uj5u.com 2021-10-16 12:36:47 more
  • 當庫存數量為0時,Recyclerview專案顯示空位

    當我從回應中得到庫存數量為0時,產品不顯示,但產品位置在網格回收器視圖kotlin中顯示空位。我將整個串列傳入配接器,然后通過庫存數量過濾。
    class ProductListAdapter(
    va...

    uj5u.com 2021-10-16 12:36:15 more
  • Android-從另一個片段內的回收器視圖呼叫片段

    我有一個應用程式(Java),原來有5個部分。所有這些都是片段,它們由底部導航中的5個圖示訪問。然而,其中一個部分(Lessons)現在被一個不同的片段所取代,該片段包含一個回收器視圖。在...

    uj5u.com 2021-10-16 12:35:50 more