这周主要对数论知识的框架和主要内容进行了整体的学习，理论部分在csdn上参考了一些博客，同时看了一部分老师发的资料。
一、莫比乌斯函数
1.定义：首先我们要先认识莫比乌斯反演，它的定义为：
其中即为莫比乌斯函数，整理即可得到莫比乌斯函数公式：
也可以表示为设，
从反演到理解莫比乌斯函数，感觉还是很困难的，一个反演就看了好几天，但感觉真的很难想通，看了好几篇博客，感觉这一篇比较好理解，ps：（定义知道怎么回事了，但从推演到证明还是不会，之后主要看了题目，了解了用法，因为太菜了）所以注明一下链接。https://blog.csdn.net/weixin_30318645/article/details/96231762
2.性质：
（1）当n不等于1时，n所有因子的莫比乌斯函数值的和为0
（2) μ(1)=1
（3)当n存在平方因子时，μ(n)=0
（4)当n是素数或奇数个不同素数之积时，μ(n)=-1
（5)当n是偶数个不同素数之积时，μ(n)=1
小总结：莫比乌斯函数主要应用是通过解析题目的含义，提取题目中存在的公式，比如看到gcd=1，或者看到类似公式，就要想到应用莫比乌斯函数的性质来进行解析题目，莫比乌斯类主要是求与因子有关的性质（定义知道怎么回事了，但从推演到证明还是不会，之后主要看了题目，了解了用法）
线性筛代码求函数；
m[1] = 1; for(int i = 2; i <= n; i++){ if(!k[i]){ p[++t] = i; m[i] = -1; } for(int j = 1; j <= t && p[j]*i <= n; j++){ k[p[j]*i] = 1; if(i%p[j] == 0) break; m[i*p[j]] = -m[i]; } }例题（主要看了几道比较经典的例题，这一道看的时间长一点还算看懂）：
代码：
#include <iostream> #include <cstdio> #include <cmath> #define LL long long const LL maxn=5e6+7; const LL mod=1000000007; using namespace std; LL test,n,m,k,cnt; LL prime[maxn],not_prime[maxn]; LL f[maxn],g[maxn]; LL power(LL x,LL y) { if (y==1) return x; LL d=power(x,y/2); d=(d*d)%mod; if (y%2) d=(d*x)%mod; return d; } void getmul(LL n) { f[1]=1; for (LL i=2;i<=n;i++) { if (!not_prime[i]) { prime[++cnt]=i; g[i]=power((LL)i,k); f[i]=(g[i]+mod-1)%mod; } for (LL j=1;j<=cnt;j++) { if (i*prime[j]>n) break; not_prime[i*prime[j]]=1; if (i%prime[j]==0) { f[i*prime[j]]=(f[i]*g[prime[j]])%mod; break; } f[i*prime[j]]=(f[i]*f[prime[j]])%mod; } } for (LL i=1;i<=n;i++) f[i]=(f[i-1]+f[i])%mod; } LL calc(LL n,LL m) { LL ans=0; if (n>m) swap(n,m); for (LL i=1,last;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); ans=(LL)(ans+(n/i)*(m/i)%mod*(f[last]+mod-f[i-1])%mod)%mod; } return ans; } int main() { scanf("%lld%lld",&test,&k); getmul(maxn); while (test--) { scanf("%lld%lld",&n,&m); printf("%lld\n",calc(n,m)); } }二、费马小定理
1.内容：
假定a是一个整数，p是一个素数，而且a不是p的倍数。那么： a^(p-1)≡1 (mod p)
另一种表示：若一个数p是素数，a为整数，且gcd(a,p) == 1
2.性质：
费马小定理只是素数判定的一个必要条件，素数一定满足费马小定理，满足费马小定理的数，却不一定是素数。
例外：Carmichael数（Carmichael数都是符合费马小定理的，但是他们都是合数）
3.应用：
（1）判断一个很大的数是否是素数，需进行优化，以避免Carmichael数。
对费马定理优化：尽可能的提取p-1中的因子2，把p-1表示为d*2^r，若p为素数，则a^d mod p = 1，或者存在一个i使得a^(d*2^i) % mod p = p-1 (0 <= i < r)。
（2）费马小定理求逆元：若一个数 M 是素数，则任意整数 A（要求gcd(A, M) == 1） 关于 M 的逆元就是 pow(A, M-2)，以此求前缀和。
4.样板例题：
题意： 给你一个数n 你要找出他的最大组成方案
思路：
如果要将2 的n-1次方的次方给降下来，那么我们可以用费马小定理，因为a^(p-1) %p=1，所以2^(mod-1)%mod 肯定也等于
1 那么我们就可以将n-1降到mod之内，方法便是 -1然后取模mod-1，便可以转化成快速幂。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N =1e5+5; const ll mod=1e9+7; string s; int num[N]; ll chuli() { ll ans=0; for(int i=0;i<s.length();i++) num[i]=s[i]-'0'; int len=s.length(); for(int i=0;i<len;i++){ ans*=10; ans+=num[i]; ans%=(mod-1); } //cout<<ans<<endl; ans-=1; ans=(ans+mod-1)%(mod-1); //cout<<ans<<endl; return ans; } ll quick_pow(ll a,ll k) { ll ans=1; while(k) { if(k&1) { ans=(ans*a)%mod; } a=(a*a)%mod; k/=2; } return ans%mod; } int main() { while(cin>>s) { ll k=chuli(); ll ans=quick_pow(2,k); ans=(ans+mod)%mod; cout<<ans<<endl; } return 0; }
