数论学习总结 | 各种模板

挖坑

欧拉筛法(过程中求欧拉函数)+求一个数的欧拉函数

 7 bool isPrime[N];
 8 ll prime[N],Eu[N];
 9 void euler(ll Range)
10 {
11     ll cntPrime=0;
12     memset(isPrime,1,sizeof(isPrime));
13     isPrime[1]=0;
14     for (ll i=2;i<=Range;i++)
15     {
16     if (isPrime[i]) prime[++cntPrime]=i,Eu[i]=i-1;
17     for (int j=1;j<=cntPrime && prime[j]*i<=Range;j++)
18     {
19         isPrime[prime[j]*i]=0;
20         if (i%prime[j]==0)
21         {
22         Eu[i*prime[j]]=Eu[i]*prime[j];
23         break;
24         }
25         Eu[i*prime[j]]=Eu[i]*(prime[j]-1);
26     }
27     }
28 }
29 int oula(int n)
30 {
31     int ans=n,a=n;
32     for(int i=2;i*i<=n;i++)
33     {
34     if(a%i==0)
35     {
36         ans-=ans/i;
37         while(a%i==0)
38         a/=i;
39     }
40     }
41     if(a>1) ans-=ans/a;
42     return ans;
43 }

EXGCD

1 ll exGcd(ll a,ll b,ll &x,ll &y)
2 {
3     if (b==0) return x=1,y=0,a;
4     ll r=exGcd(b,a%b,y,x);
5     y-=(a/b)*x;
6     return r;
7 }

因为ax+by=1 → ax+by+ab-ab=1 → a(x+b)+b(y+a)=1

所以在求出一个可行解x之后,不断的把x+-b仍是该方程的一个解,利用这个性质可以求类似最小解的问题

给出A,B,C 求最小的x满足A^x=B (mod C)

BSGS问题

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 typedef long long ll;
  6 using namespace std;
  7 ll x,z,k;
  8 ll Gcd(ll x,ll y)
  9 {
 10     return y==0?x:Gcd(y,x%y);
 11 }
 12 ll exGcd(ll a,ll b,ll &x,ll &y)
 13 {
 14     if (b==0) return x=1,y=0,a;
 15     ll r=exGcd(b,a%b,y,x);
 16     y-=a/b*x;
 17     return r;
 18 }
 19 ll inv(ll a,ll m)
 20 {
 21     ll x,y;
 22     exGcd(a,m,x,y);
 23     return (x%m+m)%m;
 24 }
 25 namespace Hash
 26 {
 27     const ll N=50000;
 28     const ll H=999979;
 29     struct adj
 30     {
 31     ll nxt,v,num,val;
 32     }e[N];
 33     ll  head[H],ecnt=0;
 34     void init()
 35     {
 36     ecnt=0;
 37     memset(head,0,sizeof(head));
 38     }
 39     void insert(ll x,ll val)
 40     {
 41     ll org=x;
 42     x%=H;
 43     for (int i=head[x];i;i=e[i].nxt)
 44     {
 45         if (e[i].num==org)
 46         {
 47         e[i].val=val;
 48         return ;
 49         }
 50     }
 51     e[++ecnt].num=org;
 52     e[ecnt].val=val;
 53     e[ecnt].nxt=head[x];
 54     head[x]=ecnt;
 55     }
 56     ll query(ll x)
 57     {
 58     ll org=x;
 59     x%=H;
 60     for (int i=head[x];i;i=e[i].nxt)
 61         if (e[i].num==org) return e[i].val;
 62     return -1;
 63     }
 64 }
 65 ll BSGS(ll a,ll b,ll c)
 66 {
 67     ll cnt=0,G,d=1;
 68     while ((G=Gcd(a,c))!=1)
 69     {
 70     if (b%G!=0) return -1;
 71     cnt++,b/=G,c/=G;
 72     d=d*(a/G)%c;
 73     }
 74     b=b*inv(d,c)%c;
 75     Hash::init();
 76     ll s=sqrt(c*1.0);
 77     ll p=1;
 78     for (int i=0;i<s;i++)
 79     {
 80     if (p==b) return i+cnt;
 81     Hash::insert(p*b%c,i);
 82     p=p*a%c;
 83     }
 84     ll q=p,t;
 85     for (int i=s;i-s+1<=c-1;i+=s)
 86     {
 87     t=Hash::query(q);
 88     if (t!=-1) return i-t+cnt;
 89     q=q*p%c;
 90     }
 91     return -1;
 92 }
 93 int check()
 94 {
 95     for (ll i=0,j=1;i<=10;i++)
 96     {
 97     if (j==k)
 98     {
 99         printf("%lld
",i);
100         return 1;
101     }
102     j=j*x%z;
103     }
104     if (x==0)
105     {
106     puts("No Solution");
107     return 1;
108     }
109     return 0;
110 }
111 int main()
112 {
113     while (scanf("%lld%lld%lld",&x,&z,&k) && x+z+k>0)
114     {
115     x%=z,k%=z;
116     if (check()) continue;
117     ll ans=BSGS(x,k,z);
118     if (ans==-1) puts("No Solution");
119     else printf("%lld
",ans);
120     }
121     return 0;
122 }