這幾天做了幾道微不足道的數論題,感覺做法都十分的高啊,我這種僵化的思想是很難有那樣的切題知識水平的。然後做了幾道題,感覺也有點熟悉數學的那一套理論了,雖然我還是太弱,但是有點東西還是要講出來的嘛,一起談笑風生,積累人生經驗。悶聲發大財雖然好,但是是不支持的。 上面那句話看不懂就無視吧。 那麼對於數論 ...
這幾天做了幾道微不足道的數論題,感覺做法都十分的高啊,我這種僵化的思想是很難有那樣的切題知識水平的。然後做了幾道題,感覺也有點熟悉數學的那一套理論了,雖然我還是太弱,但是有點東西還是要講出來的嘛,一起談笑風生,積累人生經驗。悶聲發大財雖然好,但是是不支持的。
上面那句話看不懂就無視吧。
那麼對於數論題,我們應該如何下手呢??我總結了一些分析技巧和優化技巧,希望有用(希望考場推得出來)。
題目分析:
1.題目給的很直接了,讓你求這個那個。
以兩道同年的NOI題目為例。
反正不管怎麼樣,看完題目我就知道考什麼了(這並不能掩飾我WA幾次的事實)。一眼擴展歐幾裡得,數據規模也當然很支持。暴力枚舉m,n2擴歐就能跑過,速度較西方記者而言也不遑多讓。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; const int N = 21; int n,m,c[N],p[N],l[N]; inline int gi() { int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } inline int Abs(int x){return x>0?x:-x;} inline int gcd(int a,int b){return b?gcd(b,a%b):a;} inline void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,y,x);y-=a/b*x; } inline bool check(int i,int j,int cir) { int A=(p[i]-p[j]),B=cir,C=(c[j]-c[i]),X=0,Y=0; int d=gcd(A,B);if(C%d!=0)return true; exgcd(A,B,X,Y);B=Abs(B/d); X=((X/d*C)%B+B)%B;if(X==0)X+=B; return X>min(l[i],l[j]); } int main() { n=gi(); for(int i=1;i<=n;++i) c[i]=gi(),p[i]=gi(),l[i]=gi(),m=max(m,c[i]); for(;;++m) { int flag=1; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(!check(i,j,m)) {flag=0;i=n+1;break;} if(flag)break; } printf("%d",m); return 0; }
講真我認為應該批判一番這個出題人,本來考場時間就不多,還花個10分鐘看題,還要記住什麼軍人學者政客(噫,怎麼這麼像他)。
獨立數就是歐拉函數嘛,至於按因數數分類什麼的跟莫比烏斯函數關係並不(沒)大(有)。然後求出軍人政客後用歐拉函數的性質求出學者的個數就可以了。
這題做法還是比較神的。歐拉函數不是是積性的嘛,它又是給你的質數因數,所以你利用積性+乘法結合律,就可以寫出一個二維DP的式子。但有一個更加高的方法就是直接把答案帶進去遞推,相當於用那個DP式子的分奇偶首碼和直接算,數組都不用開。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; const LL Mod = 10000; LL Ans1,Ans2,m,k; int gi() { int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } void pL(LL x) { if(x<0)putchar('-'),pL(-x); if(x<10)putchar(x+'0'); else pL(x/10),putchar(x%10+'0'); } void pc(){putchar('\n');} LL gL() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } LL Qpow(LL d,LL z) { LL ans=1; for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod; return ans; } int main() { k=gL();m=1; for(LL i=1;i<=k;++i) { LL p=gL(),e=gL(); m=m*Qpow(p,e)%Mod; if(p==2)continue; LL ans1=(Ans1+(Ans2+1)*(p-1))%Mod; LL ans2=(Ans2+Ans1*(p-1))%Mod; Ans1=ans1;Ans2=ans2; } pL(Ans2);pc();pL(Ans1);pc();pL(((m-Ans1-Ans2-1)%Mod+Mod)%Mod); return 0; }
2.公式推導
題目給了你一個公式,但是直接算是顯然會T的,這個時候就要將公式等價化簡。這種題目SDOI以前是有的,現在他們的Oier身經百戰了,見的多了,這種問題就沒怎麼出現過了。但對於新手來說,對於對數論函數的高妙使用的熟悉還是有很大幫助的。
你看,多麼簡單的一個問題,但顯然暴力是跑不過去的,這點上不管是香港記者還是松爺也必須承認的。
那麼我們必須考慮優化(不是底層優化!)。註意到有貢獻的只有gcd,且關於gcd有一個優美的性質:gcd(a/gcd(a,b),b/gcd(a,b))=1;
就是說除了gcd之後兩個數忽然就互質了,於是個數就是歐拉那麼多個。
於是答案就是sigma(d|n) d*phi(n/d);phi線上爆算就可以了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; LL n,Ans; LL gL() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } LL get(LL x) { LL ans=x; for(LL i=2;i*i<=x;++i) if(x%i==0) { ans=ans/i*(i-1); while(x%i==0)x/=i; } if(x!=1)ans=ans/x*(x-1); return ans; } int main() { n=gL(); for(LL i=1;i*i<=n;++i) if(n%i==0) { if(i*i==n)Ans+=i*get(i); else Ans+=(i*get(n/i)+(n/i)*get(i)); } printf("%lld\n",Ans); return 0; }
2.GCD
這問的問題啊,還是太簡單,太幼稚。
一個數對(x,y)的gcd為質數p,如果假設x>y,那麼對於(x/p,y/p)而言答案就是很水的類似於上一題的操作了。
對於所有的數,我們用首碼和優化一下就可以了,答案再乘以2加上1就可以了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define Inc i*Prime[j] using namespace std; const int N = 10010000; int n,Prime[N],tot,ph[N],vis[N]; LL Q[N],Ans; int gi() { int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } LL gl() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } void prepare() { ph[1]=1; for(int i=2;i<=n;++i) { if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;} for(int j=1;j<=tot;++j) { if(Inc>N)break;vis[Inc]=1; if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]]; else{ph[Inc]=ph[i]*Prime[j];break;} } } for(int i=2;i<=n;++i) Q[i]=Q[i-1]+(LL)ph[i]; } int main() { n=gi();prepare(); for(int i=1;i<=tot;++i) Ans+=(2*(Q[n/Prime[i]])+1); printf("%lld",Ans); return 0; }
3.構建數學模型,巧妙轉化
這部分是最難的。就像數學原理人人都會,但數學題不見得人人都會做;誰都有過衝動,但有的人非要去肛坦克。一般碰到這種題目,不應及時下手,應該在草稿紙上理性分析,並且打好暴力驗證你的思想。學長傳授的人生經驗是,推一個式子打一遍,不要在過程中出現偏差。
1.儀仗隊
這道題簡直就是莫比烏斯反演的弱化版(第一象限)的弱化版(n=m)的弱化版(n<=40000)好嗎!真的不怕考場上有人打表嗎?
反正一個點能被看到就是這個點橫縱坐標的gcd=1才可以!你再只看一個上或者下三角,就是歐拉函數!水的一筆。
/************************************************************** Problem: 2190 User: Ryze Language: C++ Result: Accepted Time:24 ms Memory:1760 kb ****************************************************************/ #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define Inc i*Prime[j] using namespace std; const int N = 40100; int n,vis[N],Prime[N],ph[N],tot,Ans; int gi() { int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } void pui(int x) { if(x<10)putchar(x+'0'); else pui(x/10),putchar(x%10+'0'); } void shai() { ph[1]=1; for(int i=2;i<=n;++i) { if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;} for(int j=1;j<=tot;++j) { if(Inc>n)break;vis[Inc]=1; if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]]; else {ph[Inc]=ph[i]*Prime[j];break;} } Ans+=ph[i]; }Ans-=ph[n]-1; } int main() { n=gi();shai(); printf("%d",Ans*2+1); return 0; }
2.古代豬文
題面是很有趣的,充滿著批判的意味,仿佛是要弄出一個大新聞,讓人Excited!
在PKU的學長跟我們講這是板子合集,前提是你要看出來。
題目顯然求G的sigma{d|n}(一個組合數)次方。組合數之和做指數肯定是不支持的。因為模數是個質數,就把指數模一個phi(模數)=模數-1;又因為模數-1是個合數,且發現沒有相同質因數,就用擴展Lucas來敲。然後再打一個快速冪就可以AC這道牛逼哄哄的題目惹。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; const LL Mod = 999911659; const int N = 50010; LL n,g,M[]={0,2ll,3ll,4679ll,35617ll},Y[10]; LL J[N],A[N],Z[10]; void pL(LL x) { if(x<10)putchar(x+'0'); else pL(x/10),putchar(x%10+'0'); } LL gL() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } void prepare(LL x) { A[1]=J[0]=J[1]=1; for(LL i=2;i<x;++i) J[i]=J[i-1]*i%x,A[i]=((-(x/i)*A[x%i])%x+x)%x; } LL C(LL N,LL M,LL P) { if(N<M)return 0ll; LL ans=J[N]; ans*=A[J[M]];ans%=P; ans*=A[J[N-M]];ans%=P; return ans; } LL Lucas(LL N,LL M,LL P) { if(!M)return 1ll; if(N<P&&M<P)return C(N,M,P); LL c=C(N%P,M%P,P);if(!c)return 0ll; LL L=Lucas(N/P,M/P,P);return c*L%P; } LL get(LL mod) { LL ans=0; for(LL i=1;i*i<=n;++i) if(n%i==0) { ans+=Lucas(n,i,mod);ans%=mod; if(i*i!=n)ans+=Lucas(n,n/i,mod),ans%=mod; } return ans; } LL Qpow(LL d,LL z) { LL ans=1; for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod; return ans; } int main() { n=gL();g=gL()%Mod; if(g==0){pL(0);return 0;} for(int t=1;t<=4;++t) { prepare(M[t]); Y[t]=get(M[t]); Z[t]=((Mod-1)/M[t])*A[((Mod-1)/M[t])%M[t]]; Y[0]+=Y[t]*Z[t]%(Mod-1);Y[0]%=(Mod-1); } return pL(Qpow(g,Y[0])),0; }
3.圓上的整點
這題真是神了系列。
首先你會想到a^2+b^2=r^2之枚舉a看b。現在我們來想想優化。
a^2+b^2=r^2;
a^2=r^2-b^2;
a^2=(r+b)(r-b);
令d = gcd(右邊); // 神奇思想。左式為完全平方數,就在右邊構建完全平方數。
a^2=d^2*[(r+b)/d]*[(r-b)/d];
因為右邊是完全平方數,兩中括弧內的數互質,所以本身就是完全平方數。
令其分別為p^2,q^2;
則有: p^2+q^2=2r/d;
所以你就可以直接枚舉了。枚舉d,再枚舉p或者q就好。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) #define fa (x >> 1) #define MID LL mid=(l+r)>>1 #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) using namespace std; LL Ans,r,R,p,q,A,B,X,Y,d; LL gi() { LL x=0,res=1;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')res=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar(); return x*res; } LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);} int main() { R=gi();r=2*R; for(d=1;d<=sqrt(r);++d) { if(r%d==0) { LL K1=r/d;K1/=2;K1=sqrt(K1); for(q=1;q<K1;++q) { p=sqrt(r/d-q*q); if(p*p+q*q==r/d) { A=p*p;B=q*q; if(gcd(A,B)!=1 || A==B)continue; else Ans++; } } LL K2=d;K2/=2;K2=sqrt(K2); for(q=1;q<=K2;++q) { p=sqrt(d-q*q); if(p*p+q*q==d) { A=p*p;B=q*q; if(gcd(A,B)!=1 || A==B)continue; else Ans++; } } } } cout<<4*Ans+4; }
優化技巧
1.數論分塊。
我們經常推公式推出來一個關於“取下整”的東西。其實這就是我們分塊優化的突破口。
打一個表,我們可以發現,[n/i]取下整這種東西的取值並不多,有很多連續的一段其實都是一個值。經過嚴謹的證明,大概有2√n個。
這個時候公式就可能可以得到簡化。我們用首碼和維護一下,在一段相同取值的塊內把整塊求出來,然後直接跳到下一個塊去。
公式是:
初始化:l=1,r;
分塊操作:r=n/(n/l);
下一塊:l=r+1;
這便是套路所在。有此分塊,O(n)的複雜度就被縮成了O(sqrt(n));數論分塊在莫比烏斯和數論中應用十分廣泛,考點也很多。
下麵有一道經典的數論分塊題目,涉及到分塊後的不同操作,推薦一下:
這裡放白字題解:
在此我們先瞭解正整數意義下的模運算,叫做取餘運算。
n%p 可以用式子 n-(n/p)*p 來等效替代(僅限於整型)。
所以原式可以化簡,具體式子我就給一神犇學長的博客。他推的比我的清楚,而且裡面有套路。
所以接下來的就是喜聞樂見的各種分塊。註意一定要一步一模。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; const LL Mod = 19940417; LL n,m,Ans; LL gL() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } inline LL sum(LL l,LL r){return (r-l+1)*(r+l)/2%Mod;} inline LL Sum(LL x){return x*(x+1)%Mod*(2*x+1)%Mod*3323403%Mod;} inline LL calc(LL A) { LL ret=0; for(LL l=1,r;l<=A;l=++r) { r=A/(A/l); ret+=(r-l+1)*A%Mod-(A/l)*sum(l,r)%Mod; ret=(ret%Mod+Mod)%Mod; } return ret; } LL cal(LL A) { LL res=0; for(int l=1,r;l<=n;l=++r) { r=min(n/(n/l),m/(m/l)); LL ans1=n*m%Mod*(r-l+1)%Mod; LL size=((Sum(r)-Sum(l-1))%Mod+Mod)%Mod; LL ans2=(n/l)*(m/l)%Mod*size%Mod; LL ans3=n*(m/l)%Mod*sum(l,r)%Mod; LL ans4=m*(n/l)%Mod*sum(l,r)%Mod; res=((res+ans1+ans2-ans3-ans4)%Mod+Mod)%Mod; } return res; } int main() { n=gL();m=gL();if(n>m)swap(n,m); LL ans1=calc(n),ans2=calc(m); Ans=ans1*ans2%Mod; LL ans3=cal(n);Ans=(Ans-ans3)%Mod; printf("%lld\n",(Ans+Mod)%Mod); return 0; }
2.未完待續... ...