暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx

A.黑客

显然这个题里只有 \(999\) 放在复杂度里是有可能对的，要么是 \(999^{2}\) 要么是 \(999^{2}\log 999\)，显然应该是前者.

考虑枚举全部的最简分数，然后乘上去，算的时候直接算当前分母/分子是最简分式的几倍（注意上下取整的选择），然后在分子分母的可取值区间取一个交集即可.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
signed main(){
//	freopen("T1.in","r",stdin);
//	freopen("test.out","w",stdout);
	int a,b,c,d,ans=0;
	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
	for(int i=1;i<=999;++i){
		for(int j=1;j<=999-i;++j){
			if(__gcd(i,j)==1){
				int l1=ceil(a*1.0/i),l2=ceil(c*1.0/j);
				int r1=floor(b*1.0/i),r2=floor(d*1.0/j);
				ans=(((i+j)*max(0ll,(min(r1,r2)-max(l1,l2)+1))%p)+ans)%p;
//				if(min(r1,r2)-max(l1,l2)>0)
//				cout<<i<<" "<<j<<" "<<max(l1,l2)<<" "<<min(r1,r2)<<" "<<endl;
			}
		}
	}
	printf("%lld\n",ans);
}

B.密码技术

你说得对但是这题我做过