网站建设温州,北京知名网站设计公司,云南省建设厅网站发文,wordpress新手优化题目要求找到给定区间的化简后分子分母的和小于1000的数字的个数
我的想法是先找到所有的满足要求的最简分数(总数不超过1e6,而且远小于),然后对询问查找每个最简分数出现的次数.
#includecstdio
#includecstring
#includealgorithm
#includecli…题目要求找到给定区间的化简后分子分母的和小于1000的数字的个数
我的想法是先找到所有的满足要求的最简分数(总数不超过1e6,而且远小于),然后对询问查找每个最简分数出现的次数.
#includecstdio
#includecstring
#includealgorithm
#includeclimits
#includecctype
#includequeue
#includesetusing namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e35; struct node
{int x,y;
}aa[MAXN*MAXN];
int tot;int gcd(int a,int b)
{return b0?a:gcd(b,a%b);
}void init()
{tot0;for(int i1;i999;i){aa[tot].x1; aa[tot].yi;tot;}for(int i2;i999;i){aa[tot].xi; aa[tot].y1;tot;}for(int i2;i1000;i){for(int j2;j1000;j){if(ij1000) break;if(gcd(i,j)!1) continue;aa[tot].xi; aa[tot].yj;tot;}}
}ll A,B,C,D;
ll ans,k1,k2,k3,k4;ll deal(ll a,ll b,ll c,ll d)
{if(ab || cd) return 0;if(cb || da) return 0;ll xmax(a,c);ll ymin(b,d);return y-x1;
}int main()
{//freopen(data.in,r,stdin);init();while(~scanf(%lld%lld%lld%lld,A,B,C,D)){ans0;for(int i0;itot;i){if(A%aa[i].x0) k1A/aa[i].x;else k1A/aa[i].x1;k2B/aa[i].x;if(C%aa[i].y0) k3C/aa[i].y;else k3C/aa[i].y1;k4D/aa[i].y;ll tmpdeal(k1,k2,k3,k4);if(tmp0){anstmp;//printf(%d/%d %d\n,aa[i].x,aa[i].y,tmp);}}printf(%lld\n,ans);}return 0;
}
