Hdu1573 x problem [univariate linear congruence equations]

Topic link ：

​ ​http://acm.hdu.edu.cn/showproblem.php?pid=1573​​

The main idea of the topic ：

It is less than or equal to N How many of the positive integers of X Satisfy ：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2],

 …, X mod a[i] = b[i], … (0 < a[i] <= 10).

Ideas ：

Let's find the array first b[] The least common multiple of all numbers in lcm, Then solve the one variable Linear Congruence Equations in lcm The solution in the range is a, Topic

solve x Is less than or equal to N The positive integer , Then inequality can be listed ：a + lcm * x <= N. that , If a = 0, The answer is x-1, If

a != 0, The answer is x.

AC Code ：

Log in and copy

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       __int64 
       
       GCD(
       
       __int64 
       
       a,
       
       __int64 
       
       b)
       
       
{
       
       
    
       
       if(
       
       b 
       
       == 
       
       0)
       
       
        
       
       return 
       
       a;
       
       
    
       
       else
       
       
        
       
       return 
       
       GCD(
       
       b,
       
       a
       
       %
       
       b);
       
       
}
       
       

       
       

       
       void 
       
       ExGCD(
       
       __int64 
       
       a,
       
       __int64 
       
       b,
       
       __int64 
       
       &
       
       d,
       
       __int64 
       
       &
       
       x,
       
       __int64 
       
       &
       
       y)
       
       
{
       
       
    
       
       if( 
       
       !
       
       b )
       
       
    {
       
       
        
       
       x 
       
       = 
       
       1;
       
       
        
       
       y 
       
       = 
       
       0;
       
       
        
       
       d 
       
       = 
       
       a;
       
       
    }
       
       
    
       
       else
       
       
    {
       
       
        
       
       ExGCD(
       
       b,
       
       a
       
       %
       
       b,
       
       d,
       
       y,
       
       x);
       
       
        
       
       y 
       
       -= 
       
       x 
       
       * (
       
       a
       
       /
       
       b);
       
       
    }
       
       
}
       
       

       
       

       
       __int64 
       
       A[
       
       15],
       
       B[
       
       15];
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       T,
       
       N,
       
       M;
       
       
    
       
       __int64 
       
       a,
       
       b,
       
       c,
       
       d,
       
       x0,
       
       y0,
       
       lcm;
       
       
    
       
       cin 
       
       >> 
       
       T;
       
       
    
       
       while(
       
       T
       
       --)
       
       
    {
       
       
        
       
       cin 
       
       >> 
       
       N 
       
       >> 
       
       M;
       
       
        
       
       bool 
       
       flag 
       
       = 
       
       1;
       
       
        
       
       lcm 
       
       = 
       
       1;
       
       

       
       
        
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       M; 
       
       ++
       
       i)
       
       
        {
       
       
            
       
       cin 
       
       >> 
       
       A[
       
       i];
       
       
            
       
       lcm 
       
       = 
       
       lcm 
       
       / 
       
       GCD(
       
       lcm,
       
       A[
       
       i]) 
       
       * 
       
       A[
       
       i];
       
       
        }
       
       

       
       
        
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       M; 
       
       ++
       
       i)
       
       
            
       
       cin 
       
       >> 
       
       B[
       
       i];
       
       

       
       
        
       
       for(
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       <= 
       
       M; 
       
       ++
       
       i)
       
       
        {
       
       
            
       
       a 
       
       = 
       
       A[
       
       1];
       
       
            
       
       b 
       
       = 
       
       A[
       
       i];
       
       
            
       
       c 
       
       = 
       
       B[
       
       i] 
       
       - 
       
       B[
       
       1];
       
       
            
       
       ExGCD(
       
       a,
       
       b,
       
       d,
       
       x0,
       
       y0);
       
       
            
       
       if(
       
       c 
       
       % 
       
       d 
       
       != 
       
       0)
       
       
            {
       
       
                
       
       flag 
       
       = 
       
       0;
       
       
                
       
       break;
       
       
            }
       
       
            
       
       __int64 
       
       temp 
       
       = 
       
       b 
       
       / 
       
       d;
       
       
            
       
       x0 
       
       = (
       
       x0
       
       *(
       
       c
       
       /
       
       d)
       
       %
       
       temp 
       
       + 
       
       temp) 
       
       % 
       
       temp;
       
       
            
       
       B[
       
       1] 
       
       = 
       
       A[
       
       1] 
       
       * 
       
       x0 
       
       + 
       
       B[
       
       1];
       
       
            
       
       A[
       
       1] 
       
       = 
       
       A[
       
       1] 
       
       * (
       
       A[
       
       i]
       
       /
       
       d);
       
       
        }
       
       
        
       
       if( 
       
       !
       
       flag )
       
       
        {
       
       
            
       
       cout 
       
       << 
       
       "0" 
       
       << 
       
       endl;
       
       
            
       
       continue;
       
       
        }
       
       
        
       
       __int64 
       
       Ans 
       
       = 
       
       0;
       
       
        
       
       if(
       
       B[
       
       1] 
       
       <= 
       
       N)
       
       
            
       
       Ans 
       
       = 
       
       1 
       
       + (
       
       N 
       
       - 
       
       B[
       
       1])
       
       /
       
       lcm;
       
       
        
       
       if(
       
       Ans 
       
       && 
       
       B[
       
       1] 
       
       == 
       
       0)
       
       
            
       
       Ans
       
       --;
       
       
        
       
       cout 
       
       << 
       
       Ans 
       
       << 
       
       endl;
       
       
    }
       
       

       
       
    
       
       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.
       
       
62.
       
       
63.
       
       
64.
       
       
65.
       
       
66.
       
       
67.
       
       
68.
       
       
69.
       
       
70.
       
       
71.
       
       
72.
       
       
73.
       
       
74.
       
       
75.
       
       
76.
       
       
77.
       
       
78.
       
       
79.
       
       
80.
       
       
81.
       
       
82.