Frog
思路分析:
對于0～m-1的任何一個臺階t，如果能夠被青蛙占領(lǐng)利用ext_gcd可以很快得出分析?存在k有k*gcd(ai,m)=t;
大神們的多種思路求解：
1.容斥原理＋dfs剪枝
2.容斥原理＋質(zhì)因數(shù)分解
3.歐拉函數(shù)
學(xué)到的知識點(diǎn)
1.如何判斷數(shù)據(jù)范圍1e9中數(shù)約數(shù)最多多少個霍殴？
先考慮logN／log2 的結(jié)果单寂，然后手動質(zhì)因數(shù)拆分判斷會涉及到多少個素數(shù)。
參考網(wǎng)址：自然數(shù)因數(shù)個數(shù)判斷
這個的到結(jié)果在 1e4內(nèi)笑诅，所以O(shè)(n^2)的算法是可以的调缨。
2.如果gcd(a,m)=1那么gcd(m-a,a)=1
對應(yīng)其中之一的解法 0~n與n互素的元素的求和為 sum=phi[n]*n/2
