数学问题总结
数学问题总结
公式化简
-
P2671 求和
题目大意:见原题。
这个题充分考察了数学式子的化简,以及前缀和的使用,和某逆序对问题的解题关键类似,都是式子化简。本题我还有一些化简感觉不是很自然,先占坑。
位运算相关
-
P6306 小玲的书
题目大意,有n本书,这n本书其实是好几种书,其中保证每种书的本书是k的倍数,现在我往里面再插入一本书,请求出来我插的那本书是哪种书。
我们知道,k为偶数的时候,就是一道经典的面试题,用到的是异或的思想,即由于插入了一本书,所以肯定有某种书为奇数本了。而两本相同种类的书,异或之后结果是0,所以,把所有书的种类做一个异或,最后得到的数就是新插入的书的种类。
那么k为奇数的时候呢?这里要介绍一下异或运算的本质:不进位加法。0^0=0 0^1=1 1^0=1 1^1=0,是不是?裸的异或是二进制运算,也就是说,两个一样的做异或运算,得到的是0,那么我们可以思考,能不能发明一种k进制异或运算,使得有k个一样的数进行这个运算时,结果是0呢?如果理解了不进位加法的思想,会发现这是可行的。我们把书的种类变成k进制数,然后把k的倍数本书的种类的k进制表示都做不进位加法(最后统一对k进制位取模),那么,如果这些书编号都是一样的,那么他们的k进制表示也是一样的,所以它们的每个k进制位加起来之后肯定都是k的倍数(因为是k的倍数本一样的书做不进位加法),每一位都对k取模之后肯定是0啦。所以,我们对所有的n+1本书都做k进制不进位加法,然后取模,最后把得到k进制数变回10进制,就是插入的书的种类啦。至于复杂度,如果种类最大是A,则复杂度为
O(nlog(A)) 。当然,这个题这样还过不了,因为出题人太毒瘤了,把A设得特别大,所以这道题目正解是把64位数变成4个16位数(2进制),然后对于n+1本书,看看每本书的这4个部分出现了多少次,把不是k的倍数的部分拎出来,最后一整合就是插入的书了。不进位加法思路代码如下(75pts):
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e7+8; ll n,k,ans; ll tmp[66]; int main(){ ll x; scanf("%lld %lld",&n,&k); if(k%2==0){ scanf("%lld",&ans); for(int i=2;i<=n;i++){ scanf("%lld",&x); ans=ans^x; } printf("%lld\n",ans); } else { for(int i=1;i<=n;i++){ scanf("%lld",&x); for(int j=0;x;j++,x=x/k) tmp[j]+=x%k; } for(int j=0;j<64;j++) tmp[j]%=k; for(int j=63;j>=0;j--) ans=ans*k+tmp[j]; printf("%lld\n",ans); } return 0; }正解代码如下(不需要读入优化):
#include <bits/stdc++.h> #define ll long long #define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++ using namespace std; ll n,k,ans; ll tmp[5][(1<<16)+9]; static char buf[100000],*pa(buf),*pb(buf); inline ll readint(); int main(){ ll x; n=readint(); k=readint(); // scanf("%lld %lld",&n,&k); for(int i=0;i<n;i++){ x=readint(); // scanf("%lld",&x); tmp[3][(x>>48)&0xffff]++; //统计每个数的块出现的个数 tmp[2][(x>>32)&0xffff]++; //统计每个数的块出现的个数 tmp[1][(x>>16)&0xffff]++; //统计每个数的块出现的个数 tmp[0][x&0xffff]++; //统计每个数的块出现的个数 } for(ll i=3;i>=0;i--){ for(ll j=0;j<65536;j++){ if(tmp[i][j]%k){ ans|=(j<<(i*16)); break; } } } printf("%lld\n",ans); return 0; } inline ll readint() { ll x=0;char c=gc; while(c<'0'||c>'9')c=gc; for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15); return x; }
数论
-
P1372
题目大意:从数1-n个中取出k个数,使得这k个数最大公因数最大,求这个最大公因数。
可能比较容易想到的一个方法是筛法:我可以尝试从大到小枚举这个最大公因数,然后看看能筛去哪些数,第一次枚举到的能够筛去超过k个数的数就是最大公因数了。不过这个题n的规模是1e9,会TLE。这时候我们要换方法,毕竟数论题有些就是结论嘛,说不定有一些结论可以用到。其实有了刚才筛法的经验,或许我们不难想到,要想用筛法筛出来k个数,那么这个最大公约数肯定不能大于
[\frac{n}{k}] ,不然根本筛不够k个,即gcd<=[\frac{n}{k}] 。另一方面,如果我们求出了gcd ,那么肯定是筛去了gcd,2gcd...kgcd ,如果gcd=[\frac{n}{k}] ,那么显然有kgcd<=n ,即gcd=[\frac{n}{k}] 是合法的。所以,要求的最大的gcd 就是\frac{n}{k} 了。虽然我们不一定能直接想到这个结论,但是,我们还是能够通过筛法去发现这个结论的。 -
P3951 小凯的疑惑
题目大意:对于代数式
ax+by ,已知a,b 为正整数,由输入给定,且令x,y 取遍所有非负数值,并保证这时ax+by 不能组合出来的整数c 有最大值,求这个最大的c 朴素的想法是,我们可以发现
c 的最小可能取值是max(a,b)-1 ,最大应该不会超过ab (我没独立严谨地想出来),所以我们从大到小枚举c (答案没有单调性,只能顺序枚举),每枚举一次,就做一次exgcd 来判断一下,先看有没有整数解,再看有没有正整数解,第一个不合理的c 就是答案了。这个思路可以轻易通过60\% 的数据。剩下的
40\% 的数据,a,b 很大,原算法会超时。由于我们前面的算法是基于枚举的,所以可能会比较慢,但exgcd 这个工具应该还是有必要用的,只不过需要变形一下。根据题意,如果c 求出来了,那么令d=c+1 ,ax+by=d 是有合理解的。那么,我们就是想求这样一个最大的d :ax+by=d 有合理解,且ax+by=d-1 没有合理解(这一步非常重要,是数学中的一种很常见的思路,化归的思想)。如果ax+by=d-1 也有合理解,至少有整数解,假设ax_1+by_1=d ,那么就有a(x_1-\Delta x)+b(y_1-\Delta y)=d-1 ,化简一下并带入上式有a\Delta x+b\Delta y=1 。要解出来整数\Delta x 和\Delta y ,需要gcd(a,b)=1 。也就是说如果没有gcd(a,b)=1 的话,这个题目的数据就有锅,就没法保证有最大的c 。假设题目数据没锅,那么能解出来可能的\Delta x 和\Delta y 。然后就不会分析了。偷偷看了一眼提示,由于
gcd(a,b)=1 ,所以肯定有整数解,我们现在求出两组解,一组是(x',y') ,另一组是(x'',y'') ,其中,x' 是这个方程的整数解中\Delta x 非负且最小的,y'' 是这个方程整数解中\Delta y 非负且最小的。 要想让ax+by=d-1 没有合理解,需要x_1-\Delta x 和y_1-\Delta y 中至少有一个恒为负数。如果\Delta x 取x' ,都能让x_1-\Delta x=x_1-x'<0 ,或者\Delta y 取y'' ,都能让y_1-\Delta y=y_1-y''<0 ,二者中至少有一个成立,那就肯定不会有非负整数解了。为了让d 尽可能小,我们取x_1=x'-1 ,y_1=y''-1 ,则a(x'-1)+b(y''-1) 就是我们所说的最大的d ,d-1 就是最大的不能被组合出来的数。就这样,答案就被构造出来了。虽然这个比某个很暴力一个式子就能艹过去的方法要弱,但是,能摆脱大家对于小学奥数的阴影。小学奥数做法:如果
a,b 都至少选一个的话,那么最大的ax+by 拼不出来的是ab ,怎么来的?大胆猜想,无需证明。那么如果a,b 可以不选的时候,只要在ab 的基础上减去a+b 即可了。严谨的证明这里我不再给出。我认为的标准做法代码如下:
#include <bits/stdc++.h> #define ll long long using namespace std; void exgcd(ll a,ll b,ll c,ll &x,ll &y); ll lcm(ll a,ll b); ll gcd(ll a,ll b); int main(){ ll a,b,x,y,minx,miny,k,l; scanf("%lld %lld",&a,&b); k=lcm(a,b)/a; l=lcm(a,b)/b; exgcd(a,b,1,x,y); minx=((x%k)+k)%k; miny=((y%l)+l)%l; printf("%lld\n",a*(minx-1)+b*(miny-1)-1); return 0; } ll lcm(ll a,ll b){ return (a*b)/gcd(a,b); } ll gcd(ll a,ll b){ if(b==0){ return a; } return gcd(b,a%b); } void exgcd(ll a,ll b,ll c,ll &x,ll &y){ if(b==0){ x=c; y=0; return; } exgcd(b,a%b,c,x,y); ll tmp=x; x=y; y=tmp-(a/b)*y; return; } -
CF762A
题目大意:找到n的第k小的因子(不一定是素因子),或者告知其不存在。n的规模是1e15,k的规模是1e9
根据数据范围可以知道,这道题起码要是
O(\sqrt n) 的算法,或者找规律O(1) 。如果n 有第k小的因子的话,那么要么这个因子小于等于
\sqrt n ,要么大于\sqrt n 。我们可以枚举从1到\sqrt n 的所有的数,判断是不是因子,如果在这个范围内就找到了,那么皆大欢喜,如果没找到,假如在小于等于\sqrt n 的情况下找到了m个因子,如果\sqrt n 也是n的因子的话,那么一共就有2m-1 个因子。如果2m-1<k ,则无解,否则,我们可以根据对称性,首先我们知道第k个因子以及后面的因子一共有2m-1-k+1=2m-k 个,即从右往左数,k是第2m-k 个数,所以在左边我们直接找第2m-k 个,然后被n除就好了。如果\sqrt n 不是n的因子,那么一共有2m 个因子。如果2m<k ,则无解,否则根据对称性,我们要找左边的第2m-k+1 个元素,被n除就是结果了。 -
CF776B
题目错误大意:数列
2,3,……n+1 ,每个数字都要刷上一种颜色,且如果一个数是另一个数的因子,那么这两个数要刷不同的颜色,且要尽量少用颜色。给定n ,求至少要用多少种颜色。尝试了一下知道,
n=2 时需要1种,n=3……6 时需要2种,n=7 时需要3种。这样来看,似乎和取以2为底的对数有关系。考虑了一下:给定了一个n ,然后我们写出来那个序列,现在我们截取序列的第2^i 到第2^{i+1} 项。显然,这个区间里面不可能有倍数关系,因为即使是右端点的数,也没法大于左端点的2倍,所以更不可能是其他倍了。而如果是第2^i 到第2^{i+1}+1 项,那么右端点正好是左端点的2倍,就不能使得整个区间染成同一种颜色了。然后,我也不知道对不对。然后我他妈的心态崩了!突然发现题目翻译错了!
题目正确大意:数列
2,3,……n+1 ,每个数字都要刷上一种颜色,且如果一个数是另一个数的质因子,那么这两个数要刷不同的颜色,且要尽量少用颜色。给定n ,求至少要用多少种颜色。纠正题意之后,因为有质因数,所以可能考虑线性筛。显然,质数全都涂一种颜色是可以的,而合数之间,由于不能有一个合数是另一个合数的质因子,所以合数也可以染相同的颜色。所以,当
n<3 时,1种,n>=3 时,两种。 -
P2303 连续最大公因数求和
题目大意:求
\sum\limits_{i=1}^n \gcd(i, n) 。这道题n的规模是1e9,即使是线性方法都会超时,所以必须考虑根号算法或者推公式。在这里的处理方法是用欧拉函数。我们可以发现,
\gcd(n,k)=d<=>\gcd(\frac{n}{d},\frac{k}{d})=1 。假如使得\gcd(n,k)=d 的k 有f(d) 个,那么使得\gcd(\frac{n}{d},\frac{k}{d})=1 的k 也有f(d) 个,由欧拉函数的定义知,f(d)=\phi(\frac{n}{d}) 。所以可以这样考虑这个题目:枚举gcd ,当gcd 取k 的时候,如果n\% k=0 ,则说明n 有这个因数k ,那么求f(\frac{n}{k}) ,就是求小于等于\frac{n}{d} 的且和它互质的数的个数。显然,如果某个数i 和\frac{n}{d} 互质,那么就说明gcd(n,i)=d ,所以k*f(\frac{n}{k}) 就是所有gcd(n,i)=k 的数贡献的和。顺带地,我们也可以把\frac{n}{k}*f(k) 求出来,这样的话,我们只需要枚举gcd 到\sqrt n 就好了。 -
P2155 莎拉公主的疑惑
题目大意:在
[1,n!] 中,求有多少个和m! 互质的数,结果对数r 取模。多组数据n,m 输入。题目保证了
m<=n ,所以答案组成中有一部分是\phi (m!) ,另一部分是[m!+1,n!] 之间的和m! 互素的数,并且注意到
m! 包含了[1,m] 中所有的素因子。然后又注意到一件有趣的事情:当m>=2 时,m! 是偶数,也就是说,[m!+1,n!] 中所有的偶数(即一半的数)肯定都不与m! 互素,剩下的奇数中,质数一定与m! 互素,合数看情况,要是能快速求出一个区间之内所有和某个数互素的数就好了。如果考虑欧拉函数单点求值公式的话,只要我们知道所有的小于等于
m 的素数,知道n! ,那么就可以直接求出来ans=n!*\Pi (1-\frac{1}{p_i}) ,其中p_i 取所有小于等于m 的素数。下面考虑怎么求出来这个数。显然n! 可以直接预处理+取模,1e7 之内的素数可以线性筛预处理,p_i 的逆元可以线性预处理,\Pi (1-\frac{1}{p_i})=\Pi(\frac{p_i-1}{p_i}) 在有了逆元之后可以线性预处理。都预处理好了之后,就可以O(1) 询问了。这道题给我们的启示是:如果知道一个数的素因数分解,那么就容易求出在某个区间内有多少个和它互素的数。
代码就是线性筛模板+线性求逆元模板+线性求欧拉函数模板:
#include <bits/stdc++.h> #define ll long long #define INF 9999999999 using namespace std; const int N=1e7+9; ll prime[N],inv[N],power[N],ratio[N],cnt; bool isprime[N]; ll n,m,t,mod; void getprime(); void getpower(); void getinv(); void getratio(); int main(){ scanf("%lld %lld",&t,&mod); getprime(); getpower(); getinv(); getratio(); // for(int i=1;i<50;i++){ // printf("%lld %lld %lld %lld\n",prime[i],power[i],inv[i],ratio[i]); // } while(t--){ scanf("%lld %lld",&n,&m); printf("%lld\n",(power[n]*ratio[m])%mod); } return 0; } inline void getratio(){ ratio[1]=1; for(ll i=2;i<N;i++){ if(isprime[i]){ ratio[i]=(ratio[i-1]*(((i-1)*inv[i])%mod))%mod; } else { ratio[i]=ratio[i-1]; } } } inline void getinv(){ inv[1]=1; for(ll i=2;i<N;i++){ inv[i]=((mod-mod/i)*inv[mod%i])%mod; } } inline void getpower(){ power[1]=1; for(ll i=2;i<N;i++){ power[i]=(power[i-1]*i)%mod; } } inline void getprime(){ for(ll i=2;i<N;i++){ isprime[i]=true; } for(ll i=2;i<N;i++){ if(isprime[i]){ prime[++cnt]=i; } for(ll j=1;j<=cnt && i*prime[j]<N;j++){ isprime[i*prime[j]]=false; if(i%prime[j]==0){ break; } } } } -
P4139 上帝与集合的正确用法
题目大意:见原题。
在做这道题之前,先说一下几个定理的应用。
费马小定理:若
p 为素数,则a^p\equiv a(mod\ p) ,进一步,若\gcd(a,p)=1 ,则a^{p-1}\equiv 1(mod\ p) 。欧拉定理:若
\gcd(a,n)=1 ,则a^{\phi(n)}\equiv 1(mod\ n) 。这两个定理都可以用来求
a 相对于一个模数的逆元,如果用费马小定理,则需要模数为素数;如果用欧拉定理,则需要模数与a 互素。使用时,转化为快速幂计算即可。另一个应用是,遇到求
a^b\ mod\ n 的时候,如果满足\gcd(a,n)=1 ,则可以知道a^{\phi(n)}\equiv 1(mod\ n) ,在已知这个的前提下,我们可以缩小b 的范围,即让b=b\ mod\ \phi(n) ,然后就容易计算了。本题是求
2^{2^{2{…}}}\ mod\ p ,指数大得不可想象,所以可能考虑用定理把指数控制一下,以求出值。每组询问会给出p ,但是不保证p 为质数。如果给出的p 能满足\gcd(2,p)=1 ,则可以考虑用欧拉定理,变成求2^{2^{2^{…}}mod\ \phi(p)}\ mod\ p ,这样对指数继续递归,最终\phi(p) 一定会变成\phi(2)=1 ,这个时候,显然2^{2^{2^{…}}}\ mod\ 1=0 ,在这时候就可以回溯了。但是并不是每次递归都能够让\gcd(2,p)=1 的,所以我们要考虑一个更一般的欧拉定理:若
b>=\phi(m) ,则a^b\equiv a^{b\%φ(m)+φ(m)}(mod\ m) 。并且原问题转化一下,就是求
2^x\equiv x\ (mod\ m) 。这道题也让我回忆了递归的易于理解的方法。 -
P2568 GCD
题目大意:求区间
[1,n] 内所有的无序数对(x,y) 的个数。其中(x,y) 满足\gcd(x,y) 为素数。n=1e7 有了前面几道题的经验,我们不难发现这道题的答案就是
\sum\limits _{i=1}^{n}\ \ \sum\limits _{k|i\ and\ k\ is \ prime}{\phi(\frac{i}{k})} 。不过可惜的是,这个没法像P2303一样利用对称性减少循环次数。看了题解,发现此题又是另一种想法:考虑枚举素数,把题目转化为求区间
[1,\frac{n}{p}] 内所有的\gcd(x',y')=1 的无序数对的个数,其中x=x'p,y=y'p 。这样的话O(n) 枚举p ,然后依托前缀和,O(1) 计算有多少对最大数是\frac{n}{p} 的这样的数对。关于前缀和的处理,我们要线性求出欧拉函数的前缀和,需要基于线性筛,由于每个合数都是被它最小的素因子筛去的,所以可以利用欧拉函数的两个递推公式去做,即若\gcd(p,a)=1 ,则\phi(pa)=(p-1)\phi(a) ,否则,\phi(pa)=p\phi(a) 。这样就好了。如果是有序数对呢?除了
x=y 的情况,我们都要加倍。所以,对于每个前缀和,我们乘2减1就好了。代码如下,主要是依靠线性筛线性预处理欧拉函数:
#include <bits/stdc++.h> #define ll long long #define INF 999999999999 using namespace std; const int N=1e7+9; ll n,sum[N],euler[N],prime[N],cnt,ans; bool isprime[N]; void pre(); int main(){ scanf("%lld",&n); pre(); for(ll i=0;i<cnt;i++){ ans=ans+2*sum[n/prime[i]]-1; } printf("%lld\n",ans); return 0; } void pre(){ for(ll i=2;i<=n;i++){ isprime[i]=true; } euler[1]=1; for(ll i=2;i<=n;i++){ if(isprime[i]){ prime[cnt++]=i; euler[i]=i-1; } for(ll j=0;j<cnt && i*prime[j]<=n;j++){ isprime[i*prime[j]]=false; if(i%prime[j]==0){ euler[i*prime[j]]=(prime[j])*euler[i]; break; } else { euler[i*prime[j]]=(prime[j]-1)*euler[i]; } } } for(ll i=1;i<=n;i++){ sum[i]=sum[i-1]+euler[i]; } } -
CF632D
未完待续
题目大意:有一个数列,取出一个最长的符合要求的子列,输出子列长度以及这个子列的元素。这个子列要满足的条件是:里面所有元素的最小公倍数不超过
m 。之前有一道类似的题目是:有一个集合,希望从中取出一些数,使得它们的最大公约数不是1,且取出的数尽可能多,求最多能取出来多少个数。那个题目的做法是枚举gcd,看看每次能选出来多少个数,这里是用了桶进行了优化,能够迅速知道筛掉了哪些数。
-
P6583 回首过去
未完待续
题目大意:对于
x,y\in[1,n] ,求有多少对这样的有序对(x,y) ,使得\frac{x}{y} 能写成有限小数。这道题有三档部分分,
n 的规模一个是1e3 ,一个是1e7 ,一个是1e12 。这里首先要知道一件事情:之所以一个分数
\frac{x}{y} 能够化成有限小数,是因为能够在保证分子为整数的情况下把化成10^k 的形式,也就是说,化成最简分数之后,只有当x=y 或者y 只有素因子2,5 时才能将分数转化为有限小数。这样的话,朴素的想法是枚举
x,y ,然后利用\gcd 化成最简,再进行素因数分解,复杂度O(n^2log_2n) ,预计得分40pts 。由于分数化到最简之后分母只可能含有
2,5 这两种素因子,所以我们可以考虑先基于优先队列从小到大生成所有的y ,其中y<=n 且y 只可能含有2,5 这两种素因子,显然,如果这些y 作为分母,那么分子是多少都可以化为有限小数。这样的话,我们似乎可以基于最简分数,生成那些不是最简的分数。 -
P2257 YY的gcd
题目大意:给定
N, M ,求1 \leq x \leq N ,1 \leq y \leq M 且\gcd(x, y) 为质数的(x, y) 有多少对。是不是贼熟悉?那就对了,前面有道题和这个描述差不多。显然,这道题的答案是
ans=\sum\limits_{p\ \in\ prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=p] 。如果暴力计算的话,复杂度是O(tn^3logn) ,对于1e7 的数据量以及1e4 次询问是完全不可以接受的,属于无脑暴力,我甚至不确定这种做法能拿到分数。这个时候,我们要使用莫比乌斯反演简化计算。同时,这也是我第一次做莫比乌斯反演的题目。为了使用莫比乌斯反演,我们需要先构造两个数论函数。题解说有一个套路是:设
f(d) 为\gcd(i,j)=d 的数对(i,j) 的个数,则显然f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d] 。要计算f(d) ,我们需要二重循环,实在太慢,我们想优化。考虑到我们想用莫比乌斯反演,所以我们必须再构造一个函数,要么新函数求和等于f(n) ,要么f(d) 求和得到新函数。在这里,我们使用了倍数的莫比乌斯反演公式,设F(d) 表示\gcd(i,j)=kd,k\in\Z^+ 的数对(i,j) 的个数,则F(d)=\sum\limits_{d|k\ and\ k\leq\ min(m,n)}{f(k)} 。根据乘法原理,可以计算出F(d)=[\frac{n}{d}][\frac{m}{d}] 。由莫比乌斯反演,知f(d)=\sum\limits_{d|k}\mu(\frac{k}{d})F(k) ,把F(k) 带入就有f(d)=\sum\limits_{d|k}\mu(\frac{k}{d})[\frac{n}{k}][\frac{m}{k}] 。所以,ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|k}\mu(\frac{k}{p})[\frac{n}{k}][\frac{m}{k}] 。如果计算这个式子,那么复杂度就是O(tnlnn) ,比刚才好了不少,但还是太慢,能够拿到30pts ,属于高级暴力。在继续优化之前,我认为我们值得思考为什么通过莫比乌斯反演能够降低复杂度。我们本来是要计算
f(n) 的,但是利用莫比乌斯反演,我们利用F(n) 就能表示出f(n) ,而F(n) 的计算甚为简单,只需要O(1) 的时间就好了,所以相对于裸的暴力优化了O(n^2) 的复杂度。接下来继续考虑优化。对于
ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|k}\mu(\frac{k}{p})F(k) ,先换一下元,得到ans=\sum\limits_{p\ \in\ prime}\sum\limits_{k=1}^{\frac{min(m,n)}{p}}\mu(k)F(kp) ,再还原,把kp 换成T ,则ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|T}^{min(n,m)}\mu(\frac{T}{p})F(T) ,注意到这个式子里面F 函数计算时只需要考虑T 的取值,所以考虑改变枚举顺序,先枚举T 再枚举p ,这样做的好处是能把\mu 单独放在后面,而\mu 函数是积性函数,有良好的性质,可以简化计算。在改变枚举顺序之后,ans=\sum\limits_{T=1}^{min(n,m)}F(T)\sum\limits_{p\ \in\ prime\ and\ p|T}\mu(\frac{T}{p}) 。 对于内层求和,基于线性筛的思想可以预处理出来,即设g(T)=\sum\limits_{p\ \in\ prime\ and\ p|T}\mu(\frac{T}{p}) ,预处理出g 函数的值,这就是\mu 函数的妙处。这样的话,复杂度将降为O(tn) 。但是由于是多组数据访问,所以还是过不了。本做法能够拿到60pts 的好成绩了,属于高级暴力。如果想继续优化,我们就不能老老实实地枚举。注意到
F(T)=[\frac{n}{T}][\frac{m}{T}] ,可以整除分块,所以,我们对g 函数再求一次前缀和,就可以和F 函数一起利用分块了,这样复杂度O(t\sqrt n) 代码如下:
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e7+9; const int M=1e7+9; ll prime[N],cnt,t,n,m,mobius[N],ans,maxk,f[N],sum[N]; bool isprime[N]; void getprime(); int main(){ scanf("%lld",&t); getprime(); while(t--){ ans=0; scanf("%lld %lld",&n,&m); maxk=min(n,m); // // for(ll i=0;i<cnt;i++){ // for(ll j=1;j*prime[i]<=maxk;j++){ // ans+=mobius[j]*(n/(j*prime[i]))*(m/(j*prime[i])); // } // } // printf("%lld\n",ans); //30pts // for(ll i=1;i<=maxk;i++){ // ans+=(n/i)*(m/i)*f[i]; // } //60pts ll l,r; for(l=1;l<=maxk;l=r+1){ r=min(n/(n/l),(m/(m/l))); ans+=(n/l)*(m/l)*(sum[r]-sum[l-1]); } //100pts printf("%lld\n",ans); } return 0; } void getprime(){ mobius[1]=1; for(ll i=2;i<N;i++){ isprime[i]=true; } for(ll i=2;i<N;i++){ if(isprime[i]){ prime[cnt++]=i; mobius[i]=-1; } for(ll j=0;j<cnt && prime[j]*i<N;j++){ isprime[i*prime[j]]=false; mobius[i*prime[j]]=-mobius[i]; if(i%prime[j]==0){ //某个素因子次数>1 mobius[i*prime[j]]=0; break; } } } for(ll i=0;i<cnt;i++){ for(ll j=1;j*prime[i]<N;j++){ f[j*prime[i]]+=mobius[j]; } } for(ll i=1;i<N;i++){ sum[i]=sum[i-1]+f[i]; } }这个题目给我们的启示有:
- 使用莫比乌斯反演能简化和gcd有关的统计和计算问题,其原理是用一个计算量小的函数去表示计算量大的函数
- 使用莫比乌斯反演时,需要合理地设函数,一种设函数的套路是设
f(d) 为\gcd(i,j)=d 的数对的个数,然后用约数或者倍数的莫比乌斯去构造另一个函数。 -
- 改变求和顺序看似毫无作用,其实可能能够把一些计算式从内层循环拿出到外层循环,这样有利于各自处理各自的和。
- 整除分块是个好东西。
线性代数
-
三根柱子的汉诺塔,只能相邻柱移动,有n个盘子,求移动步数。
n个盘子要想移动完,需要先把n-1个盘子从第一根柱子移到第三个柱子,然后把第n个盘子移到第二个柱子,再把n-1个盘子移到第一个柱子,再把第n个盘子移到第三个柱子,再把n-1个盘子移到第三个柱子,所以,
f[n]=3f[n-1]+2 。这个题n的规模是1e9 ,所以要加速转移过程。两个方式:一是求出通项公式,然后快速幂,二是利用矩阵快速幂优化dp。