2019.10.28 CSP%您賽第四場t3
- 2019 年 10 月 28 日
- 筆記
我寫不動前兩個了。
原諒一下。
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
【題目描述】
(varphi)函數是數論中非常常用的函數。對於正整數 x，(varphi)(x) 表示不超過 x 的所有正整數
與 x 互質的個數。
現在我們對它進行一次拓展：對於正整數 x,y，定義 (varphi)(x,y) 表示不超過 y 的所有正
整數與 x 互質的個數。
現在我們給定正整數 n 和 m，對於所有不超過 n 的正整數 i，求 (varphi)(i,m)。
【輸入格式】
從文件 phi.in 中讀入數據。
輸入僅一行兩個正整數 n 和 m。
【輸出格式】
輸出到文件 phi.out 中。
輸出 n 行，每行一個整數。第 i 行表示 (varphi)(i,m)。
【樣例輸入】
11 10
【樣例輸出】
10
5
7
5
8
3
9
5
7
4
10
以上題面。
順便補一句，以上演算法可接受的複雜度是(O(nsqrt n))。
容易知道，我們枚舉所有(ileq n)時，時間複雜度是(O(n))。所以對於每個數的判斷，我們可接受的複雜度大約是(O(sqrt n))。
考慮原來做過的題類似的做法。對於一個數(i)，與這個數互質的數的本質實際上是不存在與(i)相同的質因子。所以對於每個(i)，我們用(O(sqrt n))的複雜度求出其所有質因子作為預處理；
而對於每一個求出的質因子，任何含有該質因子的數都不能貢獻到答案上。但是由於存在同時具有好幾個該數質因子的情況，考慮容斥原理：
舉個例子，如果一個數有3個質因子，設其為(a_1,a_2,a_3)，則(ans=m-m/a1-m/a2-m/a3+m/a1/a2+m/a2/a3+m/a1/a3-m/a1/a2/a3)。其中$m是最大取值個數。
同理，設一個數有k個質因子，則容易知道：
(ans=m-m/（所有奇數個a_k相乘的可能）+m/（所有偶數個a_k）相乘的可能)。
容易證明。當我們減去所有含有單個質因子的數時，我們多減去了所有嚴格含有兩個質因子的數；再加上嚴格含有兩個質因子的數，又多加了嚴格含有三個質因子的數；……以此類推，其實是(k)階維恩圖上的容斥原理。
所以我們可以用一個二進位數的每一位代表該質因子是否被選中。若選中了偶數個質因子，則加上；否則減去。
上程式碼：
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<cmath> #define rep(i,a,n) for(int i=a;i<=n;i++) #define dep(i,n,a) for(int i=n;i>=a;i--) #define int long long using namespace std; int n,m,prime[100050],idx,ans,book_prime[100050],idx1; bool is_prime[100050],book[100050],mark[100050]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } signed main() { memset(prime,-1,sizeof prime); n=read(),m=read(); rep(i,1,n) { memset(book,0,sizeof book); memset(mark,0,sizeof mark); ans=m; idx1=0; int temp=i; int qqqqqq=sqrt(i); rep(j,2,qqqqqq) { if(temp%j==0) { book_prime[++idx1]=j; while(temp%j==0) temp/=j; } } if(temp>1) book_prime[++idx1]=temp; int maxn=(1<<idx1)-1; rep(j,1,maxn) { int cnt=0; int tmp=j; int base=1; int mul=1; while(tmp) { if(tmp&1) ++cnt,mul*=book_prime[base]; ++base; tmp>>=1; } if(cnt&1)ans-=m/mul; else ans+=m/mul; } printf("%lldn",ans); } return 0; }
