Day25

Day25

今天讲的是 扩展欧几里得+逆元 ,没咋学会。。。
数论是真的难!!!(可能只是对我而言吧)
补题

逆元解释

扩展欧几里得
逆元

Problem A

Description:
度熊手上有一本字典存储了大量的单词,有一次,他把所有单词组成了一个很长很长的字符串。现在麻烦来了,他忘记了原来的字符串都是什么,神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值,由以下公式计算得到:

H(s)=∏{(i≤len(s))i=1}(Si−28) (mod 9973)

Si代表 S[i] 字符的 ASCII 码。

请帮助度熊计算大字符串中任意一段的哈希值是多少。
Input
多组测试数据,每组测试数据第一行是一个正整数N,代表询问的次数,第二行一个字符串,代表题目中的大字符串,接下来N行,每行包含两个正整数a和b,代表询问的起始位置以及终止位置。
1≤N≤1,000
1≤len(string)≤100,000
1≤a,b≤len(string)
Output
对于每一个询问,输出一个整数值,代表大字符串从 a 位到 b 位的子串的哈希值。

1
2
3
4
5
6
7
8
9
10
11
12
Sample Input
2
ACMlove2015
1 11
8 10
1
testMessage
1 1
Sample Output
6891
9240
88

开一个arr数组存入区间1到i的乘积,算[a, b]区间时只需用arr[b]/arr[a-1],然后求出arr[a-1]的逆元即可。
code:

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int MAXN = 1e5 + 7;

ll n, a, b, x, y;
ll arr[MAXN];
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(!b)
{
x = 1;
y = 0;
return a;
}
ll r = exgcd(b, a%b, x, y);
ll t = y;
y = x - (a/b) * y;
x = t;
return r;
}

ll inv(ll a, ll n)
{
ll gcd = exgcd(a, n, x, y);
return (x+n)%n;
}

int main()
{
ios::sync_with_stdio(0);
string s;

while(cin>>n)
{
cin>>s;

arr[0] = 1;
for(int i = 1; i <= s.size(); i++)
{
arr[i] = arr[i-1]*(s[i-1] - 28)%9973;
}
while(n--)
{
cin>>a>>b;
cout<<arr[b]*inv(arr[a-1], 9973)%9973<<endl;
}

}
return 0;
}

A/B

Description:
要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
Input
数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。

1
2
3
4
5
6
7
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060

code:

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
//扩展欧几里得算法
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);
int t = y;
y = x - (a / b) * y;
x = t;
return r;
}

int main()
{
int t, a, b, mod = 9973;
int x, y;
cin >> t;
while(t --)
{
cin >> a >> b;
exgcd(b, mod, x, y);
x = (x + mod) % mod;
printf("%d\n", x * a % mod);
}

return 0;
}

//试探法
#include<bits/stdc++.h>
using namespace std;

int main()
{
int t, a, b;
cin >> t;
while(t --)
{
cin >> a >> b;
for(int i = 1; i <= 9973; i ++)
{
if(((i * (b % 9973) % 9973) - a) % 9973 == 0)
{
printf("%d\n",i);
break;
}
}
}


return 0;
}

Fansblog

Description:
Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n (n-1) (n-2) (n-3) 3 2 1 . For example, 4! = 4 3 2 1 = 24 )
Input
First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)
Output
For each testcase, output an integer representing the factorial of Q modulo P.

1
2
3
4
5
Sample Input
1
1000000007
Sample Output
328400734

题意

就是问一个质数p,求刚好不大于p的质数q的阶乘对p取模的值
首先我们要知道威尔逊定理:对于一个质数p,(p - 1) ! % p = p - 1
于是,我们可以得出
q ! (q+1) (q + 2) (p - 2) (p - 1) % p = p-1
现在答案就很明显了,ans = (p - 1)
inv(p - 1) inv(p - 2) inv(q + 2) inv(q + 1)
q的话就直接暴力求就好了,然后还要注意一下
code:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int check(ll x)
{
if (x == 1 || !x) return 0;
if (x == 2) return 1;
ll r = sqrt(x);
for (ll i = 3;i <= r;i ++)
if (x % i == 0) return 0;
return 1;
}
ll ksc(ll a,ll b,ll p)
{
return (a*b-(ll)((long double)a/p*b)*p+p)%p;
}
ll qpow(ll a,ll b,ll p)
{
ll ans = 1;
while (b)
{
if (b & 1) ans = ksc(ans,a,p);
b >>= 1;
a = ksc(a,a,p);
}
return ans;
}
ll inv(ll x,ll p)
{
return qpow(x,p-2,p);
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while (t --)
{
ll p;
cin>>p;
ll ans = p-1;
for (ll x = p - 2;;x -= 2)
{
if (check(x))
{
for (ll i = x + 1;i < p;i ++)
ans = ksc(ans,inv(i,p),p);
cout<<ans<<'\n';
break;
}
}
}
return 0;
}

Romantic

Description:
Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy Xa + Yb = 1. If no such answer print “sorry” instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put “sorry” instead.

1
2
3
4
5
6
7
8
Sample Input
77 51
10 44
34 79
Sample Output
2 -3
sorry
7 -3

很明显的exgcd,如果gcd != 1时就sorry,因为要求的x为非负数,所以写一个while每次加b即可。
code:

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
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return r;
}

int main()
{
int a, b, x, y;
while(~scanf("%d %d",&a, &b))
{
int ans = exgcd(a, b, x, y);
if(ans != 1) puts("sorry");
else
{
while(x < 0)
{
x += b;
y -= a;
}
printf("%d %d\n", x, y);
}
}

return 0;
}

Integer Divisibility

Description:
If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit. Now you are given the number and the only allowable digit, you should report the number of digits of such multiple.

For example you have to find a multiple of 3 which contains only 1’s. Then the result is 3 because is 111 (3-digit) divisible by 3. Similarly if you are finding some multiple of 7 which contains only 3’s then, the result is 6, because 333333 is divisible by 7.

Input
Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case will contain two integers n (0 < n ≤ 106 and n will not be divisible by 2 or 5) and the allowable digit (1 ≤ digit ≤ 9).

Output
For each case, print the case number and the number of digits of such multiple. If several solutions are there; report the minimum one.

1
2
3
4
5
6
7
8
9
Sample Input
3
3 1
7 3
9901 1
Sample Output
Case 1: 3
Case 2: 6
Case 3: 12

同余定理的运用,每次在原基础上乘10并加上d就可以了。
code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9;
int main()
{
int t;
ll a, b;
cin >> t;
int k = 1;
while(t --)
{
cin >> a >> b;
int cnt = 1;
ll m = b % a;
while(m)
{
m = (m * 10 + b) % a;
cnt ++;
}
printf("Case %d: %d\n", k ++, cnt);
}

return 0;
}

Large Division

Description:
Given two integers, a and b, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integer b if and only if there exists an integer c such that a = b * c.

Input
Input starts with an integer T (≤ 525), denoting the number of test cases.

Each case starts with a line containing two integers a (-10200 ≤ a ≤ 10200) and b (|b| > 0, b fits into a 32 bit signed integer). Numbers will not contain leading zeroes.

Output
For each case, print the case number first. Then print ‘divisible’ if a is divisible by b. Otherwise print ‘not divisible’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sample Input
6
101 101
0 67
-101 101
7678123668327637674887634 101
11010000000000000000 256
-202202202202000202202202 -101
Sample Output
Case 1: divisible
Case 2: divisible
Case 3: divisible
Case 4: not divisible
Case 5: divisible
Case 6: divisible

大数取模,和上一题差不多,需要注意的是保存a的值用long long类型,因为在乘的过程中可能会爆int。
code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
string str;
ll mod;
cin >> t;
int k = 1;
while(t --)
{
cin >> str;
cin >> mod;
int len = str.size();
ll ans = 0;
for(int i = 0; i < len; i ++)
{
if(str[i] == '-') continue;
ans = ans * 10 + (str[i] - '0');
ans %= mod;
}
if(ans % mod)
printf("Case %d: not divisible\n", k ++);
else
printf("Case %d: divisible\n", k ++);
}


return 0;
}

青蛙的约会

Description:
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行”Impossible”

1
2
3
4
Sample Input
1 2 3 4 5
Sample Output
4

详细题解
code:

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int MAXN = (int)1e5 +10;

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, y, x);
y -= a/b*x;
return r;
}

int main()
{
ll x, y, m, n, l;
cin>>x>>y>>m>>n>>l;
ll a, b, c, gcd;
a = m-n;
b = l;
c = y-x;
if(a<0)//使计算gcd值为正
{
a = -a;
c = -c;
}
gcd = exgcd(a, b, x, y);
if(c%gcd != 0)//这样得不到整数解
puts("Impossible");
else
{
x = x*c/gcd;
ll t = b/gcd;
cout<<(x%t+t)%t<<endl;//x可能为负,这样写保证了值为正
}

return 0;
}

Candy Distribution

Description:
Kids like candies, so much that they start beating each other if the candies are not fairly distributed. So on your next party, you better start thinking before you buy the candies.

If there are K kids, we of course need K⋅X candies for a fair distribution, where X is a positive natural number. But we learned that always at least one kid looses one candy, so better be prepared with exactly one spare candy, resulting in (K⋅X)+1 candies.

Usually, the candies are packed into bags with a fixed number of candies C. We will buy some of these bags so that the above constraints are fulfilled.

Input
The first line gives the number of test cases t (0<t<100). Each test case is specified by two integers K and C on a single line, where K is the number of kids and C the number of candies in one bag (1≤K,C≤109). As you money is limited, you will never buy more than 109 candy bags.

Output
For each test case, print one line. If there is no such number of candy bugs to fulfill the above constraints, print “IMPOSSIBLE” instead. Otherwise print the number of candy bags, you want to buy. If there is more than one solution, any will do.

1
2
3
4
5
6
7
8
9
10
11
12
13
Sample Input 1
5
10 5
10 7
1337 23
123454321 42
999999937 142857133
Sample Output 1
IMPOSSIBLE
3
872
14696943
166666655

题解

根据题意,我们可以推出来 Cans + 1 = Kx
易知 Kx - Cans = 1,即ax + by = gcd(a,b)
所以对于gcd(K , C) == 1,我们用扩展欧几里得求出一个ans,否则输出impossible
但是要注意求出的ans是负数的话要通过加K变为正的,然后对于C = 1 的情况要输出K+1
code:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if (!b)
{
x = 1,y = 0;
return a;
}
int r = exgcd(b,a%b,x,y);
int tmp = y;
y = x - (a / b) * y;
x = tmp;
return r;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while (t --)
{
ll a,b,x,y;
cin>>a>>b;
ll _ = exgcd(a,b,x,y);
if (_ != 1) cout<<"IMPOSSIBLE"<<'\n';
else
{
if (b == 1)
{
cout<<a+1<<'\n';
continue;
}
while (y <= 0) y += a;
cout<<y<<'\n';
}
}
return 0;
}

---------------- The End ----------------
0%