大水题,枚举 \(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;
}