首页 > 其他分享 >Mathematical Circus-数论-分类讨论

Mathematical Circus-数论-分类讨论

时间:2022-08-31 15:48:56浏览次数:57  
标签:Mathematical even ab 数论 4t Circus int div

codeforces Mathematical Circus-div2-B

题意:

给定n,k。是否能把(1--n)的数分成符合条件的(a,b)对。

条件:(a+k)*b%4==0

解:

因为:原式=(a+k)*b≡0(mod 4)

ab+b*k≡0(mod 4)

若k>=4,bk=b*(4t+k-4t)=4t*b+b*(k-4t)

上式有:ab+b*k≡ab+b*(k-4t)+b*4t≡ab+b*(k-4t)≡0(mod 4)

也就是说,我们只需要研究k=0,1,2,3的情况

k=0时,即:ab%4==0,不妨令a is odd,b is even,式子显然不成立

k=1 or 3:一种可能是:a+k is even,b is even,这是总可以成立的

k=2:1:a is even ,b is odd then a+k is even but not always is div by 4

2: when b==4t,t>=1,is right . other  b is odd,a+k is div by 4,a just is div by 2,but not div by 4.

#include<iostream>
#include<cstring>
#define maxn (int)(2e5+1e1)
using namespace std;
int main()
{
    int t; cin >> t;
    while (t--)
    {
        int n, k; cin >> n >> k;
        while (k > 4)k %= 4;
        if (k == 0)
        {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        if (k == 1 || k == 3)
        {
            for (int i = 1; i <= n - 1; i += 2)
            {
                cout << i << " " << i + 1 << "\n";
            }
        }
        else if (k == 2)
        {
            for (int i = 1; i <= n - 1; i += 2)
            {
                if ((i + 1) % 4 == 0)cout << i << " " << i + 1 << "\n";
                else cout << i + 1 << " " << i << "\n";
            }
        }
    }
    return 0;
}

 

标签:Mathematical,even,ab,数论,4t,Circus,int,div
From: https://www.cnblogs.com/FeiShi/p/16643293.html

相关文章

  • CF1C Ancient Berland Circus
    给定\(3\)个点,求以这\(3\)个点为顶点的正多边形面积最小值。先以这张图为例,首先可以肯定圆的半径是确定的。根据秦九韶公式,有\(S_{\triangleABC}=\sqrt{p(p-a)(p......
  • 数论笔记(Full Version)
    数论笔记(FullVersion)一、数论基础:1、整除:重新定义除法:对于计算式:\(a\divb\)来说,其结果可以变化为以下的式子:$$a=\lfloor\frac{a}{b}\rfloor+a\bmodb$$其......
  • CF1719B Mathematical Circus
    题链:cfluogu分类讨论思想。Description把\(1\)到\(n\)共\(n\)个整数分成\(\frac{n}{2}\)对有序数对\(\left(a_i,b_i\right)\),则对于\(\forall\left(a_i,......
  • 时隔多年,再次复习 CRT(数论全家桶)
    1.CRT中国剩余定理,用来求解同余方程组\begin{cases}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\\x\equiva_3\pmod{m_3}\\…………\\x\equiva_n\pmod{m......
  • 数论做题记录
    P3811【模板】乘法逆元数据范围是只能\(\mathcal{O}(n)\)过的。考虑递推逆元。设\(t=p/i,k=p%i\)。\(t*i+k\equiv0(\bmodp)\).\(k\equiv-t*......
  • 数论笔记(1)
    1、模运算的性质:加法:\[(A+B)\,mod\,C=(A\,mod\,C+B\,mod\,C)\,mod\,C\]乘法:\[(A\timesB)\,mod\,C=[(A\,mod\,C)\times(B\,mod\,C)]\,mod\,C\]减法:\[(A-B)......
  • 基础数论模板
    快速幂longlongqpow(longlonga,longlongb){ longlongans=1; for(;b;b>>=1) { if(b&1) ans=ans*a%p; a=a*a%p; } returnans;}线性筛......
  • 数论---高斯消元
    1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cmath>5usingnamespacestd;6constdoubleac=1e-8;7constintN=1......
  • 数论----同余方程
    《贝祖定理》简单来说是:整数a,b,gcd(a,b)=d;则存在x,y使ax+by=d成立证明:  《扩展欧几里得算法》  由贝祖定理:ax+by=gcd(a,b)则:当不断取模gcd(a,b)......
  • 基础数论专题题解集(暂未全部AC)
    A-青蛙的约会题面两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它......