锐客网

  1. 首页 > 睿知 > it技术 > >

[校内赛3-2][题解]matrix

原题洛谷P2158
本题出来就是防止你们AK的
首先，大家应该很容易发现这是原题（我都讲过），然后准备好了线性筛欧拉函数的模板
然后仔细一看：不对！n,m不相等，不能套板子！
只好乖乖枚举了，这样最好是O(nlogn)，可以得60分（可以参照洛谷题解）
那么正解是什么呢？相信参照题解的同学们（如果有）一定看到了一个奇奇怪怪的算法：莫比乌斯反演！
今天我们要讲的就是这个
-莫比乌斯函数
-莫比乌斯反演
-整除分块优化
推荐blog：莫比乌斯反演基础，关于gcd的反演
这里模数也是个坑，很容易写顺手
std：
[校内赛3-2][题解]matrix
文章图片
[校内赛3-2][题解]matrix
文章图片

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #define LL long long 15 #define rg register 16 #define us unsigned 17 #define eps 1e-6 18 #define INF 0x3f3f3f3f 19 #define ls k<<1 20 #define rs k<<1|1 21 #define tmid ((tr[k].l+tr[k].r)>>1) 22 #define nmid ((l+r)>>1) 23 #define Thispoint tr[k].l==tr[k].r 24 #define pushup tr[k].wei=tr[ls].wei+tr[rs].wei 25 #define pub push_back 26 #define lth length 27 using namespace std; 28 inline void Read(LL &x){ 29LL f=1; 30char c=getchar(); 31x=0; 32while(c<'0'||c>'9'){ 33if(c=='-')f=-1; 34c=getchar(); 35} 36while(c>='0'&&c<='9'){ 37x=(x<<3)+(x<<1)+c-'0'; 38c=getchar(); 39} 40x*=f; 41 } 42 #define N 10000010 43 #define mod 19268017 44 LL n,m,ans,Mu[N],Pri[N],Isntpri[N]; 45 inline void Prime(LL n){//线性筛莫比乌斯函数 46Mu[1]=1; 47for(rg LL i=2; i<=n; i++){ 48if(!Isntpri[i])Pri[++Pri[0]]=i,Mu[i]=-1; 49for(rg LL j=1; j<=Pri[0]&&i*Pri[j]<=n; j++){ 50Isntpri[i*Pri[j]]=1; 51if(i%Pri[j]==0)break; 52Mu[i*Pri[j]]=-Mu[i]; 53 //这句话其实是Mu[i*Pri[j]]=Mu[i]*Mu[Pri[j]] 54} 55} 56 } 57 int main(){ 58freopen("matrix.in","r",stdin); 59freopen("matrix.out","w",stdout); 60Read(n),Read(m); 61n--,m--; 62if(!n||!m){//特判 63if(!n&&!m)cout<<0<
My Beautiful Code 【[校内赛3-2][题解]matrix】

    推荐阅读


    上一篇：红尘

    下一篇：Android零基础入门第23节（ImageButton和ZoomButton使用大全）