首先說一下貢獻(xiàn)的思想：

舉個(gè)例子：已知有n個(gè)數(shù)，從?，求?中所有質(zhì)因數(shù)出現(xiàn)的個(gè)數(shù)。

假設(shè)當(dāng)前數(shù)為??6， 7， 5， 5， 4， 9， 9， 1， 8， 12

• 首先寫出他每個(gè)數(shù)的質(zhì)因數(shù)：

每個(gè)數(shù)的質(zhì)因數(shù)分解

6	7	5	5	4	9	9	1	8	12
2，3	7	5	5	2	3	3	0	2	2，3

• 那么求任意區(qū)間質(zhì)因數(shù)的個(gè)數(shù)，就可以轉(zhuǎn)化為求解每個(gè)數(shù)在任意區(qū)間所作的貢獻(xiàn)度。

求解貢獻(xiàn)度

序號	1	2	3	4	5	6	7	8	9	10
ai	6	7	5	5	4	9	9	1	8	12
質(zhì)因數(shù)	2，3	7	5	5	2	3	3	0	2	2，3
貢獻(xiàn)度	(10) + (10)	9 + 9	8 + 8 + 8	7	6 + 6 + 6 + 6	5 + 5 + 5 + 5	4	0	2+2+2+2	1 + (1 + 2)

（求解貢獻(xiàn)度時(shí)要注意前面已經(jīng)出現(xiàn)和計(jì)算過的數(shù)字不在計(jì)算，防止重復(fù)。如：質(zhì)因數(shù)2的貢獻(xiàn)，在序號為1處出現(xiàn)質(zhì)因數(shù)為2，此時(shí)他的貢獻(xiàn)度為：

? ? ? ? [1, 1] , [1, 2], [1, 3] , [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9],? [1, 10]

在序號為5處出現(xiàn)質(zhì)因數(shù)2，此時(shí)他的貢獻(xiàn)度為：

? ? ? ? [1, 5](這個(gè)已經(jīng)被計(jì)算過一次，舍去)

? ? ? ? ? ?實(shí)際貢獻(xiàn)度：[5, 5] , [5, 6] , [5, 7] , [5, 8] , [5, 9] , [5, 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[2, 5] , [2, 6] , [2, 7] , [2, 8] , [2, 9] , [2 , 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[3, 5] , [3, 6] ,?[3, 7] , [3, 8] , [3, 9] ,?[3, 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[4, 5] , [4, 6] , [4, 7] , [4, 8] , [4, 9] ,?[4, 10]

在序號為9處出現(xiàn)質(zhì)因數(shù)2， 此時(shí)他的貢獻(xiàn)度為：

? ? ? ? ? 實(shí)際貢獻(xiàn)度： [9, 9] , [9, 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[6, 9] , [6, 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[7, 9] , [7, 10]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[8, 9] , [8, 10]

在序號為10處出現(xiàn)質(zhì)因數(shù)2，此時(shí)他的貢獻(xiàn)度為：

? ? ? ? 實(shí)際貢獻(xiàn)度：? [10, 10]

）

好處：

如果直接使用暴力的算法的話，時(shí)間復(fù)雜度為，避免不了求區(qū)間的情況，但如果使用求貢獻(xiàn)度的思維去求，可以在O(n)的時(shí)間復(fù)雜度內(nèi)完成

然后就是求解每個(gè)數(shù)的質(zhì)因數(shù)分解：

可以直接用埃式篩法來得到：

const int maxn = 1e6+5; int vis[maxn]; vector<int>v[maxn]; void init(){memset(vis, 0, sizeof(vis));for(int i = 2; i < maxn; i++){if(!vis[i]){v[i].push_back(i);for(int j = 2*i; j < maxn; j += i){vis[j] = 1;v[j].push_back(i);}}} }

然后就很好求解了。。。。。。。

?

一道例題：

?

這道題就是一道求貢獻(xiàn)度的題，只要理解上面就很好求解了：

#include<bits/stdc++.h>using namespace std; typedef long long LL;const int maxn = 1e6+5; int vis[maxn]; vector<int>v[maxn]; vector<int>pos[maxn]; int n; int a[maxn];void init(){memset(vis, 0, sizeof(vis));for(int i = 2; i < maxn; i++){if(!vis[i]){v[i].push_back(i);for(int j = 2*i; j < maxn; j += i){vis[j] = 1;v[j].push_back(i);}}} }int main() {init();scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);LL ans = 0;for(int i = 1; i <= n; i++){if(a[i] == 1) continue;int tmpnum = v[a[i]].size();for(int j = 0; j < tmpnum; j++){int now = v[a[i]][j];if(pos[now].size() == 0){ans += 1LL * (n - i + 1) * i;pos[now].push_back(i);}else{vector<int>::iterator it = pos[now].end(); it--;int tmppos = *it;ans += 1LL * (n - i + 1) * (i - tmppos);pos[now].push_back(i);}}}printf("%lld\n", ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的贡献思想 + 数论 + 思维（例题 Problem J. Prime Game）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。