• 【T】03


    A 【模板】快速幂

    板子,略

    #include
    #define ll long long
    using namespace std;
    ll a,p,k;
    int main()
    {
    	scanf("%lld%lld%lld",&a,&p,&k);
    	printf("%lld^%lld mod %lld=",a,p,k);
    	ll ans=1,w=a;a%=k;
    	while(p)
    	{
    		if(p&1)
    		{
    			ans=ans*w%k;
    		}
    		w=w*w%k;
    		p>>=1;
    	}printf("%lld",ans%k);
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    B【模板】矩阵快速幂

    #include
    using namespace std;
    long long mod=1000000007;
    long long n,k;
    struct sq{
    	long long num[102][102];
    	sq(){memset(num,0,sizeof(num));}//初始化num数组为空
    };
    sq operator *(const sq &a,const sq &b)
    {
    	sq ans;
    	for(int k=1;k<=n;k++)
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;
    		}
    	}return ans;
    }//一个重载
    sq x,y,ans;
    long long read()
    {
    	char s;long long ans=0;
    	s=getchar();
    	while(s>'9'||s<'0'){s=getchar();}
    	while(s>='0'&&s<='9')
    	{
    		ans=ans*10+s-'0';
    		s=getchar();
    	}
    	return ans;
    }//只是个快速读入函数
    inline void init()
    {
    	n=read();k=read();//用scanf,cin也行
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			x.num[i][j]=read();
    	for(int i=1;i<=n;i++)
    	{
    			y.num[i][i]=1;
    			ans.num[i][i]=1;
    	}
    }
    int main(){
    	init();
    	while(k)
    	{
    		if(k&1){ans=ans*x;}
    		x=x*x;
    		k>>=1;
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    			printf("%lld ",ans.num[i][j]);
    		printf("\n");
    	}
    	   return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    C【模板】有理数取余
    除以一个数等于乘以它的逆元,逆元可以用费马小定理
    数据很大,读入采用快读的同时取模(对于a,b来说不影响答案)

    #include
    #define ll long long 
    using namespace std;
    ll a,b,mod=19260817;
    inline ll read()
    {
    	ll ans=0;char s=getchar();
    	while(s>'9'||s<'0')s=getchar();
    	while(s>='0'&&s<='9')
    	{
    		ans=((ans<<1)%mod+(ans<<3)%mod+(s&15))%mod;
    		s=getchar();
    	}return ans;
    }
    ll quick_m(ll i,ll n)
    {
    	i%=mod;
    	ll ans=1,ds=i;
    	while(n)
    	{
    		if(n&1)
    		{
    			ans=ans*ds%mod;
    		}
    		ds=ds*ds%mod;
    		n>>=1;
    	}return ans%mod;
    }
    signed main(){
    	a=read();b=read();
    	if(b==0){printf("Angry!");return 0;}
    	printf("%lld",a*quick_m(b,mod-2)%mod);
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    D 质因数分解

    #include
    int a;
    int main()
    {
    	scanf("%d",&a);
    	for(int i=2;i*i<=a;i++)
    	{
    		if(a%i==0)
    		{
    			printf("%d",std::max(a/i,i));
    			return 0;//找到一个因数就可以停了,另一个因数就是最大的那个
    		}
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    E 质数筛
    数据不大的话,每个数都直接用质数判断法也能过

    #include
    using namespace std;
    int n,a;
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            bool f=1;
            for(int j=2;j*j<=a;j++)
            {
                if(a%j==0){f=0;break;}
            }
            if(f==1&&a!=1)printf("%d ",a);//是质数
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    F 【模板】线性筛素数
    这里用的欧拉筛

    #include
    using namespace std;
    bool ans[100000002];
    int z[6000005],p;
    int n,m,a;
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=2;i<=n;i++)
    	{
    		if(!ans[i])z[++p]=i;//printf("[%d]",z[p]);
    		for(int j=1;j<=p&&z[j]*i<=n;j++)
    		{
    			ans[i*z[j]]=1;
    			if(i%z[j]==0)break;
    		}
    	}
    	for(int i=1;i<=m;i++)
    	{
    		scanf("%d",&a);
    		printf("%d\n",z[a]);
    	}
    	return 0;
    } 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    G 晨跑
    求三个数的最小公倍数

    #include
    #define ll long long
    using namespace std;
    ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
    ll lcm(ll x,ll y){return x*y/gcd(x,y);}
    int main()
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        printf("%lld",lcm(a,lcm(b,c)));
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    H 最大公约数和最小公倍数问题
    x ∗ y = g c d ( x , y ) ∗ l c m ( x , y ) x*y=gcd(x,y)*lcm(x,y) xy=gcd(x,y)lcm(x,y)
    枚举x然后判断算出对应y是否满足gcd,lcm就行,可能要特判

    #include
    #define ll long long
    using namespace std;
    ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
    ll lcm(ll x,ll y){return x*y/gcd(x,y);}
    int main()
    {
        ll a,b,ans=0;
        scanf("%lld%lld",&a,&b);
        if(a==b)ans--;//这样会存在x,y相同的一组,下面枚举时会多算一组,故删去
        for(ll i=1;i*i<=a*b;i++)
            if(a*b%i==0&&gcd(i,a*b/i)==a)ans+=2;
        printf("%lld",ans);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    I 【模板】模意义下的乘法逆元
    建议看我之前博客线性递推式部分
    a − 1 = − ⌊ p / a ⌋ ∗ ( p   m o d   a ) − 1      ( m o d   p ) a^{-1}=-⌊p/a⌋*(p \ mod \ a )^{-1} \ \ \ \ (mod \ p) a1=p/a(p mod a)1    (mod p)

    #include
    #define ll long long 
    using namespace std;
    int n,p,inv[3000005];
    signed main(){
    	scanf("%d%d",&n,&p);
    	inv[0]=1;inv[1]=1;
    	printf("1\n");
    	for(int i=2;i<=n;i++)
    	{
    		inv[i]=(ll)inv[p%i]*(p-p/i)%p;//-p/i不能直接取模,要+p变成正数再%p
    		printf("%d\n",inv[i]);
    	}
    	return 0;
    }
    /*下面是欧拉筛版
    #include 
    #define ll long long
    using namespace std;
    const int N=3000005;
    ll n,p;
    bool vis[N];
    ll z[N];
    ll inv[N];
    ll quick(ll a,ll k,ll mod)
    {
    	ll ans=1,as=a;
    	while(k)
    	{
    		if(k&1)
    		{
    			ans=ans*as%mod;
    		}
    		as=as*as%mod;
    		k>>=1;
    	}
    	return ans;
    }
    int main()
    {
        scanf("%lld%lld",&n,&p);
        vis[1]=1,inv[1]=1;
        for (int i=2;i<=n;i++)
        {
            //printf("(%d\n",i);
            if (!vis[i])z[++z[0]]=i,inv[i]=quick(i,p-2,p);
            for (int j=1;j<=z[0]&&i*z[j]<=n;j++)
            {
                vis[i*z[j]]=1;
                inv[i*z[j]]=(inv[i]*inv[z[j]])%p;
                if (i%z[j]==0) break;
            }
        }
        for (int i=1;i<=n;i++)
        printf("%lld\n",inv[i]);
        return 0;
    }*/
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    J 沙拉公主的困惑
    1 − > N ! 1->N! 1>N!中与 M ! M! M!互质的个数

    推演一下,最后得 N ! M ! ϕ ( M ! ) \frac {N!}{M!} \phi{(M!)} M!N!ϕ(M!)
    => N ! ( 1 − p 1 p 1 ) ( 1 − p 2 p 2 ) . . . ( 1 − p k p k ) N!(\frac {1-p_1}{p_1})(\frac {1-p_2}{p_2})...(\frac {1-p_k}{p_k}) N!(p11p1)(p21p2)...(pk1pk)
    一堆预处理,质数+线性求逆+阶乘。。。

    #include
    #define ll long long 
    using namespace std;
    inline ll read()
    {
    	ll ans=0;char s=getchar();
    	while(!isdigit(s))s=getchar();
    	while(isdigit(s))
    	{
    		ans=(ans*10)+(s&15);
    		s=getchar();
    	}return ans;
    }
    const int N=1e7+10;
    int T;
    ll n,m,mod;
    int z[N],p;
    bool vis[N];
    void get_prime()
    {
    	for(int i=2;i<N;i++)
    	{
    		if(!vis[i])z[++p]=i;
    		for(int j=1;j<=p&&i*z[j]<N;j++)
    		{
    			vis[i*z[j]]=1;
    			if(i%z[j]==0)break;
    		}
    	}
    }
    ll inv[N],mul[N],pt[N];
    int main()
    {
    	scanf("%d%lld",&T,&mod);
    	get_prime();
    	inv[1]=1;inv[0]=1;
    	for(int i=2;i<N;i++)
    		inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    	mul[1]=1;
    	for(int i=2;i<N;i++)
    		mul[i]=mul[i-1]*i%mod;
    	pt[1]=1;
    	for(int i=2;i<N;i++)
    		if(!vis[i])
    			 pt[i]=pt[i-1]*(i-1)%mod*inv[i%mod]%mod;
    		else pt[i]=pt[i-1];
    	while(T--)
    	{
    		n=read();m=read();
    		printf("%lld\n",mul[n]*pt[m]%mod);
    	}
    }//开个o2就过了
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    K 同余方程
    扩欧板子题

    #include
    using namespace std;
    void gcd(int a,int b,int &x,int &y)
    {
    	if(!b)
    	{
    		x=1;y=0;
    		return ;
    	}
    	gcd(b,a%b,x,y);
    	int xx=y,yy=x-a/b*y;
    	x=xx;y=yy;
    	return ;
    }
    int a,b,x,y;
    int main()
    {
    	scanf("%d%d",&a,&b);
    	gcd(a,b,x,y);
    	printf("%d",(x+b)%b);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
  • 相关阅读:
    Unity 编辑器扩展 一键替换指定物体下的所有材质球
    虚拟机VirtualBox和Vagrant安装
    vue3+vite
    GaussDB数据库SQL系列-表连接(JOIN)
    Ansible stat模块 stat模块 – 检索文件或文件系统状态
    Linux服务器挂载另一台服务器的文件夹(mount)
    React-Redux
    Linux虚拟机中网络连接的三种方式
    Hbase之动态切换HMaster
    Django与Ajax
  • 原文地址:https://blog.csdn.net/ygmjsjdboy/article/details/134061722