題目：http://acm.hdu.edu.cn/showproblem.php?pid=1695

?

題意：給定五個(gè)數(shù)，其中有和，求滿足條件的有序?qū)Φ膫€(gè)數(shù)。題目中

???? 明確說在所有的輸入中。

?

分析：問題可以轉(zhuǎn)化為和時(shí)，的有序?qū)Φ膫€(gè)數(shù)。那么先比較和的

???? 大小，相同的部分可以用歐拉函數(shù)的累加計(jì)算，沒有公共的部分用容斥計(jì)算即可。

?

???? 當(dāng)然，在用容斥計(jì)算時(shí)，對(duì)于每一個(gè)數(shù)要進(jìn)行dfs，這樣必然會(huì)對(duì)每一個(gè)數(shù)進(jìn)行素因子分解，實(shí)際上我們可以對(duì)

???? 每一個(gè)數(shù)進(jìn)行線性篩，從而計(jì)算出它的所有素因子以及每一個(gè)素因子出現(xiàn)的次數(shù)，這樣預(yù)處理時(shí)間快很多。

?

代碼：

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 100005; typedef long long LL;LL phi[N]; int num[N]; int p[N][15];void Init() {memset(num,0,sizeof(num));memset(phi,0,sizeof(phi));phi[1] = 1;for(int i=2;i<N;i++){if(!phi[i]){for(int j=i;j<N;j+=i){if(!phi[j]) phi[j] = j;phi[j] = phi[j] - phi[j] / i;p[j][num[j]++] = i;}}phi[i] += phi[i-1];} }LL dfs(int x,int r,int n) {LL ans = 0;for(int i=x;i<num[n];i++)ans += r / p[n][i] - dfs(i+1,r/p[n][i],n);return ans; }int main() {Init();int tt = 1;int T;scanf("%d",&T);while(T--){int a,b,k;scanf("%d%d%d%d%d",&a,&a,&b,&b,&k);if(a > b) swap(a,b);if(k == 0){printf("Case %d: 0\n",tt++);continue;}a /= k;b /= k;LL ans = phi[a];for(int i=a+1;i<=b;i++)ans += a - dfs(0,a,i);printf("Case %d: %I64d\n",tt++,ans);}return 0; }

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的欧拉函数与容斥的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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