当前位置:网站首页>AcWing 1298. Solution to Cao Chong's pig raising problem
AcWing 1298. Solution to Cao Chong's pig raising problem
2022-07-06 11:16:00 【Octopus loving monster】
AcWing 1298 . Cao Chong raises pigs Answer key
Title Description
Since Cao Chong got the elephant , Cao Cao began to think about letting his son do something , So he was sent to Zhongyuan pig farm to raise pigs , But Cao Chong was very unhappy , So in the work of careless , Once Cao Cao wanted to know the number of sows , So Cao Chong wanted to play with Cao Cao .
for instance , If there is 16 16 16 A sow , If it's built 3 3 3 A pigsty , be left over 1 1 1 There's no place for a pig to settle down ; If you build 5 5 5 A pigsty , But there is still 1 1 1 A pig has no place to go ; If you build 7 7 7 A pigsty , also 2 2 2 The head has no place to go .
As Mr. Cao's personal secretary, you should report the accurate pig number to Mr. Cao , What are you gonna do? ?
Input format
The first line contains an integer n n n, Indicates the number of times to establish a pigsty ;
Next n n n That's ok , Two integers per line a i , b i a_i,b_i ai,bi Indicates that the a i a_i ai A pigsty , Yes b i b_i bi There's no place for a pig .
You can assume that a i , a j a_i,a_j ai,aj Coprime
Output format
The output contains only one positive integer , That is, at least the number of pigs raised by Cao Chong
Data range
1 ≤ b ≤ 10 1\le b \le 10 1≤b≤10
1 ≤ b i ≤ a i ≤ 1100000 1\le b_i\le a_i\le 1100000 1≤bi≤ai≤1100000
all a i a_i ai The product of does not exceed 1 0 18 10^{18} 1018
Answer key
The test point of this question is Chinese remainder theorem
We describe the Chinese surplus in the following form
Here we give the method of calculating Chinese Remainder Theorem and prove
Calculate the product of all modules n n n
For the first i i i An equation :
a. Calculation m i = n n i m_i=\dfrac{n}{n_i} mi=nin
b. Calculation m i m_i mi In the mold n i n_i ni Inverse element in sense m i − 1 m_i^{-1} mi−1
c. Calculation c i = m i × m i − 1 c_i =m_i\times m_i^{-1} ci=mi×mi−1 ( incorrect n i n_i ni modulus )
The unique solution of the system of equations is : x = ∑ i = 1 k a i c i ( m o d n i ) x=\sum^k_{i=1}a_i~c_i (mod ~n_i) x=∑i=1kai ci(mod ni)
prove :
We can prove the result obtained by this method x x x For arbitrary i = 1 , 2 , … , k i=1,2, \dots,k i=1,2,…,k All meet x ≡ a i ( m o d n i ) x ~\equiv~ a_i~(mod~n_i) x ≡ ai (mod ni)
When i ≠ j i\neq j i=j when , Yes
m j ≡ 0 ( m o d n i ) m_j \equiv 0~(mod~ n_i) mj≡0 (mod ni)
For
c j ≡ m j ≡ 0 ( m o d n i ) c_j \equiv m_j \equiv 0 ~(mod ~n_i) cj≡mj≡0 (mod ni)
According to
c i = m i × m i − 1 ≡ 1 ( m o d n i ) c_i = m_i\times m_i^{-1}\equiv 1~(mod~n_i) ci=mi×mi−1≡1 (mod ni)
For x x x Yes
x ≡ ∑ j = 1 k a j c j ( m o d n i ) ≡ a i c i ( m o d n i ) ≡ a i × 1 ( m o d n i ) ≡ a i ( m o d n i ) x\equiv\displaystyle\sum_{j=1}^ka_j c_j ~~~~~~(mod ~n_i) \\ \equiv a_ic_i~~\qquad(mod n_i) \\ \equiv a_i\times1~~~~~~(mod n_i) \\ \equiv a_i~~~~~\qquad(mod n_i) x≡j=1∑kajcj (mod ni)≡aici (modni)≡ai×1 (modni)≡ai (modni)
Obtain evidence
Find the inverse element in the sense of module
Then the idea of this topic becomes very clear , Now the question is how Find the inverse element in the sense of module
Let's look at a formula
a a − 1 ≡ 1 ( m o d c ) aa^{-1} \equiv 1~(mod ~c) aa−1≡1 (mod c)
Deformation can be obtained
a a − 1 = k c + 1 aa^{-1} = kc+1 aa−1=kc+1
transposition
a a − 1 − k c = 1 aa^{-1} -kc =1 aa−1−kc=1
It is observed that it is shaped like Euclidean equation
a x + b y = c ax+by=c ax+by=c
Therefore, it can be solved by extended Euclidean
Complete code
import java.io.*;
import java.util.*;
class Main
{
static long sum=1;
static int n;
static int[] a=new int[10];
static int[] c=new int[10];
static long x;
static long y;
static long res=0;
public static long exgcd(long a,long b)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long d=exgcd(b,a%b);
long tmp=x;
x=y;
y=tmp-(a/b)*x;
return d;
}
public static void main(String[] agrs)throws IOException
{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(reader.readLine());
for(int i=0;i<n;i++)
{
String[] param=reader.readLine().split(" ");
c[i]=Integer.parseInt(param[0]);
a[i]=Integer.parseInt(param[1]);
sum*=c[i];
}
for(int i=0;i<n;i++)
{
long m=sum/c[i];
long re=exgcd(m,c[i]);
res=(res+a[i]*m*x%sum)%sum;
}
System.out.println((res%sum+sum)%sum);// Output positive numbers
}
}
边栏推荐
- Postman Interface Association
- PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
- ++Implementation of I and i++
- Did you forget to register or load this tag
- 软件测试-面试题分享
- Invalid default value for 'create appears when importing SQL_ Time 'error reporting solution
- 安全测试涉及的测试对象
- [recommended by bloggers] asp Net WebService background data API JSON (with source code)
- @Controller, @service, @repository, @component differences
- Classes in C #
猜你喜欢
Did you forget to register or load this tag
QT creator support platform
error C4996: ‘strcpy‘: This function or variable may be unsafe. Consider using strcpy_s instead
Some problems in the development of unity3d upgraded 2020 VR
CSDN Q & a tag skill tree (V) -- cloud native skill tree
AI benchmark V5 ranking
Csdn-nlp: difficulty level classification of blog posts based on skill tree and weak supervised learning (I)
[recommended by bloggers] C # generate a good-looking QR code (with source code)
解决安装Failed building wheel for pillow
一键提取pdf中的表格
随机推荐
Swagger, Yapi interface management service_ SE
安装numpy问题总结
Swagger、Yapi接口管理服务_SE
La table d'exportation Navicat génère un fichier PDM
Use dapr to shorten software development cycle and improve production efficiency
Introduction to the easy copy module
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
MySQL主從複制、讀寫分離
Base de données Advanced Learning Notes - - SQL statements
Ansible practical series I_ introduction
Did you forget to register or load this tag 报错解决方法
Ansible实战系列一 _ 入门
Unable to call numpy in pycharm, with an error modulenotfounderror: no module named 'numpy‘
一键提取pdf中的表格
Installation and use of MySQL under MySQL 19 Linux
解决:log4j:WARN Please initialize the log4j system properly.
连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
Mysql 其他主机无法连接本地数据库
A brief introduction to the microservice technology stack, the introduction and use of Eureka and ribbon