题解 黑客

传送门

大水题,枚举 \(z\) 的大小,计算出现次数即可

Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define int long long

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline ll read() {
	ll ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

ll a, b, c, d;
const ll mod=1e9+7;
inline void md(ll& a, ll b) {a+=b; a=a>=mod?a-mod:a;}
inline ll gcd(ll a, ll b) {return !b?a:gcd(b, a%b);}

namespace force{
	ll ans;
	void solve() {
		for (ll i=a; i<=b; ++i) {
			for (ll j=c; j<=d; ++j) {
				ll k=gcd(i, j), z=i/k+j/k;
				if (z<1000) md(ans, z);
			}
		}
		printf("%lld\n", (ans%mod+mod)%mod);
		exit(0);
	}
}

namespace task1{
	ll ans;
	void solve() {
		for (int k=1; k<1000; ++k) {
			for (int i=1,j; i<k; ++i) {
				j=k-i;
				if (gcd(i, j)!=1) continue;
				ll l1=(a-1)/i+1, r1=b/i, l2=(c-1)/j+1, r2=d/j;
				ll l=max(l1, l2), r=min(r1, r2);
				if (l<=r) {
					ans=(ans+(r-l+1)%mod*k%mod)%mod;
					// cout<<"lr: "<<l<<' '<<r<<' '<<k<<endl;
					// cout<<"ij: "<<i<<' '<<j<<endl;
				}
			}
		}
		printf("%lld\n", ans);
		exit(0);
	}
}

signed main()
{
	freopen("hacker.in", "r", stdin);
	freopen("hacker.out", "w", stdout);

	a=read(); b=read(); c=read(); d=read();
	// force::solve();
	task1::solve();

	return 0;
}
上一篇:A


下一篇:数论 专题整理