威尼斯国际平台app 体育教学 中国剩余定理是用来解同余方程组,●TPU表层超强耐磨防滑处理 ●高强度聚脂网格布稳定层

中国剩余定理是用来解同余方程组,●TPU表层超强耐磨防滑处理 ●高强度聚脂网格布稳定层

天速乒乓球地板TS500

Switch case必得与break一同使用

扩充中黄炎子孙民共和国剩余定理详明,中华夏儿女民共和国定律详细解释

●TPU表层超强耐磨防滑处理 ●高强度聚脂网格布牢固层

Break 是跳转语句。与switch case连用的时候是跳出方今的{}。

前言

阅读本文前,推荐先学一下华夏剩余定理。其实不学也不留意,毕竟两者没啥关系

宝石红 长20m×宽1.8m×厚5.0mm

 

扩展CRT

我们领略,中华夏族民共和国剩余定理是用来解同余方程组

$$begin{cases}xequiv c_{1}left( mod m_{1}right) \
xequiv c_{2}left( mod m_{2}right) \ ldots \ xequiv
c_rleft( mod m_rright) end{cases}$$

然而有二个要命让人超级慢的事情就是它要求$m_1,m_2ldots,m_r$两两互素

假如有个别恶性癌症出题人偏供给它们部互素呢?

实则也是有减轻的艺术

尽管把出题人吊起来干大器晚成顿用扩张中华夏族民共和国剩余定理

扩充中华夏族民共和国剩余定理跟中黄炎子孙民共和国剩余定理没半毛钱关系,一个是用扩大欧几里得,三个是用布局

 

率先大家依旧从简单入手,思谋一下要是同余方程组唯有七个姿态的境况

$xequiv c_{1}left( mod m_{1}right) \ xequiv c_{2}left(
mod m_{1}right)$

将四个姿态变形

$x=c_{1}+m_{1}k_{1}\ x=c_{2}+m_{2}k_{2}$

联立

$c_{1}+m_{1}k_{1}=c_{2}+m_{2}k_{2}$

移项

$m_{1}k_{1}=c_{2}-c_{1}+m_{2}k_{2}$

大家用$(a,b卡塔尔(قطر‎$表示$a,b$的最大契约数

在那地须求注意,这一个方程有解的尺码是

$left( m_{1},m_{2}right) |left(
c_{2}-c_{1}right卡塔尔(قطر‎$,因为背后会用到$dfrac {left(
c_{2}-c_{1}right) }{left( m_{2},m_{1}right卡塔尔国}$那生机勃勃项,假若不整除的话肯定会现身小数。

对于地点的方程,两侧同除$(m_1,m_2)$

$$dfrac {m_{1}k_{1}}{left( m_{1},m_{2}right) }=dfrac
{c_{2}-c_{1}}{left( m_{1},m_{2}right) }+dfrac
{m_{2}k_{2}}{left( m_{1},m_{2}right) }$$

$$dfrac {m_{1}}{left( m_{1},m_{2}right) }k_{1}=dfrac
{c_{2}-c_{1}}{left( m_{1},m_{2}right) }+dfrac {m_{2}}{left(
m_{1},m_{2}right) }k_{2}$$

改造一下

$$dfrac {m_{1}}{left( m_{1},m_{2}right) }k_{1} equiv dfrac
{c_{2}-c_{1}}{left( m_{1},m_{2}right) } (mod dfrac
{m_{2}}{left( m_{1},m_{2}right) })$$

此时大家早已打响把$k_2$消去了。

同余式两侧同除$dfrac {m_{1}}{left( m_{1},m_{2}right) }$

$$k_1equiv inv({m_1over(m_1,m_2)},{m_2over
(m_1,m_2)})*{(c_2-c_1)over (m_1,m_2)}pmod
{{m_2over(m_1,m_2)}}$$

$inv(a,b卡塔尔(英语:State of Qatar)$表示$a$在模$b$意义下的逆元

$$k_1=inv({m_1over(m_1,m_2)},{m_2over
(m_1,m_2)})*{(c_2-c_1)over (m_1,m_2)}+{{m_2over
(m_威尼斯国际平台app ,1,m_2)}}*y$$

接下去如何做吧?那么些姿势已经化到最简了。。

毫不要忘记了,大家刚开首还会有八个姿态。我们把$k_1$待回去!

$$x=inv({m_1over(m_1,m_2)},{m_2over
(m_1,m_2)})*{(c_2-c_1)over (m_1,m_2)}*m_1+y{{m_1m_2over
(m_1,m_2)}}+c_1$$

$$xequiv inv({m_1over(m_1,m_2)},{m_2over
(m_1,m_2)})*{(c_2-c_1)over (m_1,m_2)}*m_1+c_1pmod
{{m_1m_2over (m_1,m_2)}}$$

此刻,整个式子中的成分我们都早已驾驭了

现实一点,那个姿势能够作为是$$xequiv cpmod m$$

其中$$c=(inv({m_1over (m_1,m_2)},{m_2over
(m_1,m_2)})*{(c_2-c_1)over (m_1,m_2)})%{m_2over
(m_1,m_2)}*m_1+c_1$$

$$m={m_1m_2over (m_1,m_2)}$$

 

扩充一下

小编们每回把八个同余式合併,求解之后收获八个新的同余式。再把新的同余式和任何的联立,最后就足以求出知足条件的解

 

static void Main(string[]args )

代码

主题素材链接

#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;
const LL MAXN=1e6+10;
LL K,C[MAXN],M[MAXN],x,y;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0){x=1,y=0;return a;}
    LL r=exgcd(b,a%b,x,y),tmp;
    tmp=x;x=y;y=tmp-(a/b)*y;
    return r;
}
LL inv(LL a,LL b)
{
    LL r=exgcd(a,b,x,y);
    while(x<0) x+=b;
    return x;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    while(~scanf("%lld",&K))
    {
        for(LL i=1;i<=K;i++) scanf("%lld%lld",&M[i],&C[i]);
        bool flag=1;
        for(LL i=2;i<=K;i++)
        {
            LL M1=M[i-1],M2=M[i],C2=C[i],C1=C[i-1],T=gcd(M1,M2);
            if((C2-C1)%T!=0) {flag=0;break;}
            M[i]=(M1*M2)/T;
            C[i]= ( inv( M1/T , M2/T ) * (C2-C1)/T ) % (M2/T) * M1 + C1;
            C[i]=(C[i]%M[i]+M[i])%M[i];
        }
        printf("%lldn",flag?C[K]:-1);
    }
    return 0;
}

 

 

再放道裸题

题解

前言
阅读本文前,推荐先学一下中华剩余定理。其实不学也不留意,终归两个没啥关系
增加CRT 大家…

{

  //switch case 多用于年月日的简政放权

  int cs=1;

  switch(cs卡塔尔(قطر‎//小括号内是四个数据类型的值

    {

       //case 后加空格,之后写上跟上边小括号内对应类型可能出现的值

      case 1://cs值为1,则实行着一步,展现case 1

         Console.WriteLine(“case 1”);

         
break;//间距break如今的大括号,跳出这么些大括号,试行大括号之后的下令

      case 2:

         Console.WriteLine(“case 2”);

          break;

      default://如若值跟上边的case 1,case 2都区别盟,则进行这一步

         Console.WriteLine(“default case “);

         break;

    }

console.ReadLine();

}

 

 

练习

//输入日期,决断是当年的第几天············
//1 3 5 7 8 10 12
//4 6 9 11
//2
int m1 = 31, m3 = 31, m5 = 31, m7 = 31, m8 = 31, m10 = 31, m12 = 31, m4
= 30, m6 = 30, m9 = 30, m11 = 30, m2 = 28;
Console.WriteLine(“输入要询问的月度”卡塔尔国;
int m = int.Parse(Console.ReadLine());
Console.WriteLine(“输入要查询的日期”卡塔尔(英语:State of Qatar);
int day = int.Parse(Console.ReadLine());
switch (m)
{
case 1:
Console.WriteLine(“您输入的日子是” + m + “-” + day + “是现年的第” + day

  • “天”);
    break;
    case 2:
    Console.WriteLine(“您输入的日子是” + m + “-” + day + “是二零一四年的第” + (m1
  • day) + “天”);
    break;
    case 3:

Console.WriteLine(“您输入的日期是” + m + “-” + day + “是现年的第” + (m1

  • m2 + day) + “天”);
    break;
    case 4:
    Console.WriteLine(“您输入的日期是” + m + “-” + day + “是二〇一三年的第” + (m1
  • m2 + m3 + day) + “天”);
    break;
    case 5:
    Console.WriteLine(“您输入的日子是” + m + “-” + day + “是现年的第” + (m1
  • m2 + m3 + m4 + day) + “天”);
    break;
    case 6:
    Console.WriteLine(“您输入的日子是” + m + “-” + day + “是今年的第” + (m1
  • m2 + m3 + m4 + m5 + day) + “天”);
    break;
    case 7:
    Console.WriteLine(“您输入的日子是” + m + “-” + day + “是当年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + day) + “天”);
    break;
    case 8:
    Console.WriteLine(“您输入的日期是” + m + “-” + day + “是现年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + m7 + day) + “天”);
    break;
    case 9:
    Console.WriteLine(“您输入的日期是” + m + “-” + day + “是当年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + m7 + m8 + day) + “天”);
    break;
    case 10:
    Console.WriteLine(“您输入的日期是” + m + “-” + day + “是现年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + m7 + m8 + m9 + day) + “天”);
    break;
    case 11:
    Console.WriteLine(“您输入的日期是” + m + “-” + day + “是今年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + m7 + m8 + m9 + m10 + day) + “天”);
    break;
    case 12:
    Console.WriteLine(“您输入的日子是” + m + “-” + day + “是现年的第” + (m1
  • m2 + m3 + m4 + m5 + m6 + m7 + m8 + m9 + m10 + m11 + day) + “天”);
    break;
    default:
    Console.WriteLine(“您的输入有误”卡塔尔;
    break;
    }
标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图