擴充歐幾裡得+逆元題解

A：

開一個arr數組存入區間1到i的乘積，算[a, b]區間時隻需用arr[b]/arr[a-1]，然後求出arr[a-1]的逆元即可。

#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;
}
           

B：

闆子。

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

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, n, b, x, y;
	cin>>t;
	while(t--)
	{
		cin>>n>>b;
		int r = exgcd(b, 9973, x, y);
		cout<<(n*(x+9973)%9973)%9973<<endl;
	}

	return 0;
}
           

C：

川佬做了題解：

https://blog.csdn.net/cloudy_happy/article/details/99571628

D：

很明顯的exgcd，如果gcd != 1時就sorry，因為要求的x為非負數，是以寫一個while每次加b即可。

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

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 a, b, x, y;
	while(cin>>a>>b)
	{
		int r = exgcd(a, b, x, y);
		if(r != 1)
            cout<<"sorry"<<endl;
        else
        {
            while(x<0)
            {
                x += b;//實際上是x += b/r
                y -= a;
            }
            cout<<x<<' '<<y<<endl;
        }
	}

	return 0;
}
           

E：

同餘定理的運用，每次在原基礎上乘10并加上d就可以了。

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

int main()
{
    ios::sync_with_stdio(0);
    int t, n, d;
    cin>>t;
    int pos = 1;
    while(t--)
    {
        cin>>n>>d;
        ll x = d;
        int len = 1;
        while(x%n != 0)
        {
            x = x*10+d;
            x %= n;
            len++;
        }
        cout<<"Case "<<pos<<": "<<len<<endl;
        pos++;
    }

	return 0;
}
           

F：

大數取模，和上一題差不多，需要注意的是儲存a的值用long long類型，因為在乘的過程中可能會爆int。

還有不要犯s[0] == '-'的sb錯誤。

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

int main()
{
    ios::sync_with_stdio(0);
    int t, b;
    string s;
    cin>>t;
    int pos = 1;
    while(t--)
    {
        cin>>s>>b;
        ll a = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '-') continue;
            a = a*10 + s[i] - '0';
            a %= b;
        }
        if(a == 0)
            cout<<"Case "<<pos++<<": divisible"<<endl;
        else
            cout<<"Case "<<pos++<<": not divisible"<<endl;
    }

	return 0;
}
           

G：

前幾天寫過這道題的部落格：

https://blog.csdn.net/qq_42756958/article/details/98478799

H：

川佬再次給出了題解：

https://blog.csdn.net/cloudy_happy/article/details/99585820