每日一题5.21

XinyuLin

https://qoj.ac/contest/1840/problem/9622

c题比较快的是铜牌，D题是银牌

Fengyj

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long
const int N = 1e9;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
//分数约分后分母的因子只含2和5，则为有限分数
void solve(){
    int a, b;
    cin >> a >> b;

    int e=b;
    while(e%2==0)
        e /= 2;
    while(e%5==0)
        e /= 5;

    int p = e * e;
    int ans = 1e18;

    int ans1 = 1e18, ans2 = 1e18;

    for (int x = 1; e * x <= N;x*=2){
        for (int y = 1; e * x * y <= N;y*=5){
            int d = e * x * y;
            int t = (p - a * d % p + p) % p;

            int g = gcd(b, p);
            if(t%g)
                continue;

            int c0, y0;
            g = exgcd(b, p, c0, y0);
            int c = c0 * (t / g);
            int res = (c % (p / g) + p / g) % (p / g);
            if(res<ans){
                ans = res;
                ans1 = res;
                ans2 = d;
            }
        }
    }
    cout << ans1 <<' '<<ans2<< endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

XinyuLin

快铜题
#include<bits/stdc++.h>
using namespace std;


void solve() {
        int n;
        string s[7];
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        s[0] = s[1] = s1;
        s[6] = s[5] = s2;
        int num1 = count(s1.begin(), s1.end(), '#');
        int num2 = count(s2.begin(), s2.end(), '#');
        if (num1 == n || num2 == n) {
                if (num1 == num2) {
                        cout << "Yes" << endl;
                        string temp(n, '#');
                        for (int i = 0; i < 7; i++) {
                                cout << temp << endl;
                        }
                }
                else {
                        cout << "No" << endl;
                }
                return;
        }

        cout << "Yes" << endl;

        for (int i = 0; i < n; i++) {
                s[1][i] ^= '.' ^ '#';
                s[5][i] ^= '.' ^ '#';
        }



        int fi1 = 0, fi2 = 0;
        string temp(n, '.');
        for (int i = 0; i < n - 1; i++) {
                if (s[1][i] ^ s[1][i + 1]) {
                        if (s[1][i] == '.') {
                                temp[i] = '#';
                                fi1 = i;
                        }
                        else {
                                temp[i + 1] = '#';
                                fi1 = i + 1;
                        }
                        break;
                }
        }
        s[2] = temp;
        temp.clear();
        temp.resize(n, '.');
        for (int i = 0; i < n - 1; i++) {
                if (s[5][i] ^ s[5][i + 1]) {
                        if (s[5][i] == '.') {
                                temp[i] = '#';
                                fi2 = i;
                        }
                        else {
                                temp[i + 1] = '#';
                                fi2 = i + 1;
                        }
                        break;
                }
               
        }
        s[4] = temp;
        temp.clear();
        temp.resize(n, '.');

        if (fi1 == fi2 || abs(fi1 - fi2) == 1) {
                temp[fi1] = '#';
        }
        else {
                if (fi1 > fi2) {
                        swap(fi1, fi2);
                }
                for (int i = fi1 + 1; i <= fi2 - 1; i++) {
                        temp[i] = '#';
                }
        }
        s[3] = temp;
        for (int i = 0; i < 7; i++) {
                cout << s[i] << endl;
        }
}


int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t--) {
                solve();
        }


        return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
vector<int>num2,num5,all;
void init(){
	num2.push_back(1);
	num5.push_back(1);
	for(;num5.back()*5<=1e9;){
		num5.push_back(num5.back()*5);
	}
	for(;num2.back()*2<=1e9;){
		num2.push_back(num2.back()*2);
	}
	for(auto i : num2){
		for(auto j:num5){
			if(i*j>1e9)continue;
			all.push_back(i*j);
//			cout<<i*j<<endl;
		}
	}
	sort(all.begin(),all.end());
}
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}else{
		int d=exgcd(b,a%b,y,x);
		//a*x1+b*y1=b*y+ax-a/b*bx
		//a*x1+b*y1=ax+b(y-a/b*x)
		//x1=x y1=y-a/b*x
		y=y-(a/b)*x;
		return d;
	}
}
void solve(){
	int a,b,c=1e18,d,m;
	cin>>a>>b;
	m=b;
	while(m%2==0)m/=2;
	while(m%5==0)m/=5;
	if(m==1){
		cout<<0<<" "<<1<<endl;
		return ;
	}
	int k=b/m%m,inv_k,xm;
	exgcd(k,m,inv_k,xm);
	int lim_s=(int)1e9/m,s;
	for(auto i : all){
		if(i>lim_s)continue;
		int c2=-a*i%m*inv_k%m;
		c2=(c2+m)%m;
		if(c>c2){
			c=c2;
			s=i;
		}
	}
	cout<<c<<" "<<s*m<<endl;

}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>t;
	init();
	while(t--)solve();
	return 0;
}

XinyuLin

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

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



void solve() {
	ll a, b;
	cin >> a >> b;
	ll w = b;
	while (w % 2 == 0) w /= 2;
	while (w % 5 == 0) w /= 5;
	ll inf = 1e9;
	ll ans = inf;
	ll ans2 = inf;
	for (ll i = 1; i * w <= inf; i *= 5) {
		for (ll j = 1; j * i * w <= inf; j *= 2) {
			ll x, y;
			ll d = exgcd(w, -b / w, x, y);
			ll cur = abs(w / d);
			y = (y * a * i * j / d % cur + cur) % cur;
			if (y < ans) {
				ans2 = i * j * w;
				ans = y;
			}
		}
	}
	cout << ans << ' ' << ans2 << endl;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}


	return 0;
}