HelloKiki(hdu3579+不互质的中国剩余定理)

作者:网络    软件教程库   2020-05-12

hello kiki

time limit:1000msmemory limit:32768kb64bit io format:%i64d %i64u

submitstatuspracticehdu 3579

appoint description:

description

one day i was shopping in the supermarket. there was a cashier counting coins seriously when a little kid running and singing 门前大桥下游过一群鸭,快来快来 数一数,二四六七八. and then the cashier put the counted coins back morosely and count again...
hello kiki is such a lovely girl that she loves doing counting in a different way. for example, when she is counting x coins, she count them n times. each time she pide the coins into several same sized groups and write down the group size mi and the number of the remaining coins ai on her note.
one day kiki‘s father found her note and he wanted to know how much coins kiki was counting.

input

the first line is t indicating the number of test cases.
each case contains n on the first line, mi(1 = i = n) on the second line, and corresponding ai(1 = i = n) on the third line.
all numbers in the input and output are integers.
1 = t = 100, 1 = n = 6, 1 = mi = 50, 0 = ai mi

output

for each case output the least positive integer x which kiki was counting in the sample output format. if there is no solution then output -1.

sample input

2 2 14 57 5 56 5 19 54 40 24 80 11 2 36 20 76

sample output

case 1: 341 case 2: 5996




先可以先找两个同余方程 设通解为n;

n=r1(mod(m1)),n=r2(mod(m2));

显然可以化为k1*m1#43;r1=k2*m2#43;r2;---k1*m1#43;(-k2*m2)=r2-r1;

设a=m1,b=m2,x=k1,y=(-k2),c=r2-r1方程可写为ax#43;by=c;

由欧几里得解得x即可,那么将x化为原方程的最小正整数解,(x*(c/d)%(b/d)#43;(b/d))%(b/d);

这里看不懂的去看解模线性方程。那么这个x就是原方程的最小整数解。

所以n=a*(x#43;n*(b/d))#43;r1====n=(a*b/d)*n#43;(a*x#43;r1),

这里只有n为未知数所以又是一个n=(a*x#43;r1)(mod(a*b/d))的式子,

然后只要不断的将两个式变成一个式子,最后就能解出这个方程组的解。

题目连接:http://acm.hdu.edu.cn/showproblem.phppid=3579

转载请注明出处:寻找星空の孩子
孩子的专栏


#includestdio.h
#define ll __int64

void exgcd(ll a,ll b,ll d,ll x,ll y)
{
    if(!b){d=a;x=1;y=0;}
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ll gcd(ll a,ll b)
{
    if(!b){return a;}
    gcd(b,a%b);
}

ll m[55],a[55];


ll china(int r)
{
    ll dm,i,a,b,x,y,d;
    ll c,c1,c2;
    a=m[0];
    c1=a[0];
    for(i=1; ir; i++)
    {
        b=m[i];
        c2=a[i];
        exgcd(a,b,d,x,y);
        c=c2-c1;
        if(c%d) return -1;//c一定是d的倍数,如果不是,则,肯定无解
        dm=b/d;
        x=((x*(c/d))%dm+dm)%dm;//保证x为最小正数//c/dm是余数,系数扩大余数被
        c1=a*x+c1;
        a=a*dm;
    }
    if(c1==0)//余数为0,说明m[]是等比数列。且余数都为0
    {
        c1=1;
        for(i=0;ir;i++)
            c1=c1*m[i]/gcd(c1,m[i]);
    }
    return c1;
}
int main()
{
    int t,n,t=0;
    scanf(%d,t);
    while(t--)
    {
        scanf(%d,n);
        for(int i=0;in;i++)
        {
            scanf(%i64d,m[i]);
        }
        for(int i=0;in;i++)
        {
            scanf(%i64d,a[i]);
        }

        ll ans=china(n);
        printf(case %d: %i64d\n,++t,ans);

    }
    return 0;
}


/*
20
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76
2
14 57
5 56
2
19 54
11 2
*/








hello kiki(hdu3579+不互质的中国剩余定理)

原文地址:http://blog.csdn.net/u010579068/article/details/45422941

软件教程库 该篇文章地址:https://www.itjcku.com/9999/1091355.html

阅读全部内容


Tags:不互质中国剩余定理

返回首页



推荐内容

android环境下摄像头数据采集及显示

以前项目涉及些摄像头预览及数据处理操作,当时的需求是除了做摄像头预览外,还要显示文字、个性图像等,当初在查找资料实 ...

uva10003CuttingSticks简单区间dp

// uva 10003 cutting sticks 区间dp // 经典的区间dp // dp(i,j)表示切割小木 ...

Go的语言特性总结

写在前面: 近来关于对golang的讨论有很多,七牛的几个大牛们也断定go语言在未来将会快速发展,并且很可能会取代ja ...

golang控制channel的出入口

golang控制channel的出入口 我们常常使用channel来在多个goroutine之间做数据通讯,但是cha ...

UVA10479TheHendrieSequence规律

题目大意:一个序列,刚开始由0变到了1,接着往后一个个变化下去 变化的规则是,如果当前数是k,就在这个序列的最后面加上 ...

在不是Activity类中调用Toast和Dialog

有时候我们需要在非activity类中处理一些逻辑,显示toast对话框或者是弹出一个dialog,但是在非activi ...

查询Oraclesql语句中绑定变量值的方法

alter session set nls_date_format = #39;yyyy-mm-dd,hh24:mi:s ...

Hdoj1588GaussFibonacci【矩阵快速幂】

gauss fibonacci time limit: 1000/1000 ms (java/others) m ...

Hdoj5195DZYLovesTopologicalSorting【拓扑】+【线段树】

dzy loves topological sorting time limit: 4000/2000 ms (jav ...

【转自mos文章】使用单条sql来查询出awr中的syatemstatistics

使用单条sql来查询出awr中的syatem statistics 参考自: how to monitor system ...

I.MX6Q(TQIMX6Q/TQE9)学习笔记——新版BSP之u-boot移植

前段时间就开始学习i.mx6q了,但是最近工作实在是忙,间断了一些时间了。为了提高移植效率,还是考虑移植freescal ...

eclipse应用技巧

最近发现eclipse作为ide还是有很多值得探索的使用技巧的,转载一下他人整理好的资源以做分享。 快捷键的使用,加速 ...

Mysql创建数据库的排序规则中文选择哪种编码

mysql中文编码 mysql创建数据库的排序规则 中文 选择哪种编码原文地址:http://blog. ...

线性表简述

一、简单实现增,删,改、查 package datatructs; /** * 表接口 */ public int ...

android测试本地服务调试流程

我今天调试的整个过程 1,安卓发现连不上本地的tomcat 2,使用浏览器直接尝试,发现可以连上 3,怀疑是安卓app和 ...

设计模式1

静态工厂模式,工厂方法模式,抽象工厂模式 工厂方法改进了添加新产品时,静态工厂不满足的开-闭原则;而抽象工厂满足了当产品 ...

c语言文件操作总结

#includelt;stdio.hgt; /********************************** ...

(c#)如果添加的字段中已经有了身份证号码,则年龄和性别和出生年月可得

//把界面文本框里面的身份证号进行提取,以二代身份证为例 model.ecardid = txt_cardno. ...

Scrum时间估算

在新公司里,不懂软件工程的产品经理经常逼迫研发人员作出很不靠谱的时间估算。常见场景有下面这些: 需求未细化的情况下要求给 ...

C++11中uniforminitialization和initializer_list

c++11中出现了uniform initialization的概念: int a1 = {1};//ok int a ...

关于Scrum

最近某些产品经理发出下两周的工作计划的时候,喜欢带上sprint这个字眼,看上去貌似是要走敏捷开发这一套,只可惜,我觉得 ...

输入输出简单解释

;汇编指令,表示程序将被汇编成能在intel386系列及以上的计算机上运行.386;model flat 表明程序使用保 ...

2015第18周五问题即机会

问题即机会,当一切问题都不存在的时候,请问你的机会在哪里? 你能达到怎样的境界,取决于你怎样认识这个世界。对于问题,有人 ...

solr配置方案

http://www.sjsjw.com/kf_cloud/article/44_5945_1823.asp cento ...

什么是二维码?

二维码,业界当然是人人听说,人人用过。 这个话题,我倒是百感交集,我一直认为,我有一种二维码情节。 一方面, 我自认 ...

1475:方格取数

1475: 方格取数 time limit:5 secmemory limit:64 mbsubmit:578solv ...

敏捷开发宣言(一)

原文: inpiduals and interactionsover processes and tools worki ...

(C#)一个项目的配置和增删改查

一、windows窗体项目环境配置步骤 1.文件mdash;gt;新建mdash;gt;项目mdash;gt;windo ...

比例简化

题目描述description 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示 ...

sockaddr和sockaddr_in的区别

struct sockaddr和struct sockaddr_in这两个结构体用来处理网络通信的地址。 在各种系统调用 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com