COCI 2010.03.06 T5「PROGRAM」 題解

洛谷題號P5190，這是學校考試的時候出的一道原題，考場上寫了一個自以為是優雅的暴力的做法，結果還a了，效率還較高。事后仔細一想得知原因，才肯定自己寫的是正解。。。

先上題面

MIRKO 寫了一段程序，并按如下方法運行這個程序。首先開了一個大小為N的數組，并賦值為零。接下來運行他的程序。程序如下：

C代碼：

void something( int jump ) {

int i = 0;

while( i < N ) {

seq[i] = seq[i] + 1;

i = i + jump;

}

}

Pascal代碼：

procedure something( jump: longint );

var i : longint;

begin

i := 0;

while i < N do

begin

seq[i] := seq[i] + 1;

i := i + jump;

end;

end;

每運行一次代碼，他都會傳入一個JUMP的值。一共運行了K次。傳入的JUMP序列可表示為X1 X2 X3... Xk 。接下來，他通過Q個詢問來來測試自己的程序是否正常工作。詢問格式如下：L，R，表示輸出數組中L到R的和，包括（L，R），你的程序要完成的就是順次輸出這Q的詢問的值。

輸入：

第一行兩個正整數 N (1 ≤ N ≤ 10^6), 表示數組的大小，and K (1 ≤ K ≤ 10^6), 表示運行代碼的次數。

第二行K個整數，表示傳入的參數值: X1X2X3 ... Xk, (1 ≤ Xi < N).

接下來一行一個整數，Q (1 ≤ Q ≤ 10^6), 表示詢問的次數。

接下來的Q行表示詢問的邊界Li Ri(0 ≤ Li≤ Ri < N)。

輸出：

共Q 行，每行一個數，表示對應的和。

樣例：

Input:

10 4

1 1 2 1

3

0 9

2 6

7 7

Output:

35

18

3

Input:

11 3

3 7 10

3

0 10

2 6

7 7

Output:

8

2

1

Input:

1000000 6

12 3 21 436 2 19

2

12 16124

692 29021

Output:

16422

28874

樣例說明：

樣例1傳入的參數是 1, 1, 2, 1.

運行后數組為{4, 3, 4, 3, 4, 3, 4, 3, 4, 3}2 to 6 的和為4+3+4+3+4=18.

樣例2的數組為。{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}.

分析題面得到思路

首先，這個奇妙的題給了我們一個函數，那么這個函數是干嘛的呢？

先來關注下標i，i初值為0，每次加上jump，說白了i=1jump , 2jump , 3* jump...n*jump (n * jump<給定的N)

說白了就是給seq數組中 下標為小于N的 jump的倍數 的元素的值 增加1（為了防止讀者被我繞暈，自行斷句）

分析樣例得知可能會有相同的數字重復出現的情況，而相同的數字在N以內的倍數是一定的，也就是說會有重復計算拖累時間。而相同的數字是可以統一處理的，只需要在seq數組中的 以相同的那個數字在N以內的倍數為下標的那幾個元素 加上那個數字重復出現的次數 （我又來主動斷句了）， 便能得到和逐個計算相同的效果。（因為計算了n次，那些元素就加了n次，做n次+1為何不直接做一次加n？）然后開一個vis數組記錄哪些數字已經被操作過，避免重復計算（第一次操作了那個數就已經相當于是操作了所有重復出現的那個數了，后面的就直接忽略了），數據保證每一個元素都小于等于10^6意味著這個方案是可行的。

因為要詢問區間的和，我就第一時間想到了維護前綴和數組，這樣比較省時間嘛，構造一個n查詢就只有1了。

標程+詳細注解

我覺得我的注解是真的寫的很良心了。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//我自己都覺得這個typedef寫的很蠢，下面就用過一次longlong，懶得改了
int n,k,q;
int seq[1000005];
ll qzh[1000005];//等價于long long qzh[1000005];
short vis[1000005];//畢竟只有0和1，省點空間。。
int jump[1000005];
int cnt[1000005];
inline int read()//快讀，感興趣的可以記一下，但是確實沒幾個題會卡你快讀
{
	char ch=getchar();
	int l=0;
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		l=l*10+ch-'0';
		ch=getchar();
	}
	return l;
}
inline bool comp(int a,int b)//sort的comp函數
{
	return a<b;
}
int main()
{
	//scanf("%d%d",&n,&k);
	n=read(),k=read();//這一句等價于上面那一句，下面的所有帶有read函數的都是這樣
	for(int i=1;i<=k;i++)
	{
		//scanf("%d",&jump);
		jump[i]=read();
		cnt[jump[i]]++;//這個就是我提到的記錄每一個數字出現了多少次的數組
	/*	*/
	}
	for(int i=1;i<=k;i++){
		if(vis[jump[i]]==0){//VIS數組就是我提到的記錄哪些數字已經被操作過，避免重復計算的數組
			for(int j=1;j<=n/jump[i];j++){
				seq[jump[i]*j]+=cnt[jump[i]];//計算了n次，那些元素就加了n次，做n次+1為何不直接做一次加n
			}
			vis[jump[i]]=1;//這個數字已經被計算過了，打上標記
		}
	}
	seq[0]=k,qzh[0]=k;//題目小坑，無論是什么數，seq[0]都會被加一次
	for(int i=1;i<=n;i++){//前綴和數組構造
		qzh[i]=qzh[i-1]+seq[i];
	}
//	scanf("%d",&q);
	q=read();
/*	for(int i=0;i<=n;i++){
		printf("%d ",seq[i]);
	}*/
	for(int i=1;i<=q;i++){
		int l,r;
	//	scanf("%d%d",&l,&r);
		l=read(),r=read();
		if(l==0){
			printf("%lld\n",qzh[r]);
			continue;
		}
		printf("%lld\n",qzh[r]-qzh[l-1]);//注意是l-1千萬不要寫成l了！
	}
}

為什么不會TLE

我最開始也是想，這玩意不是少了幾次的n^2嘛？能過？

那是因為約數個數性質

O(N+N\2+N\3+......+N\N)=O(Nlog N)

所以這本質上是NlogN級別的，會TLE有鬼叫（嗷嗷嗷~~~~)

寫在最后

還是感謝您能看到這里！

最近考試會比較多可能寫題解也會比較多啦。。

挖的坑。。可能不打算補了。。