#include #include #include #include #include #include using namespace std; typedef long long LL; inline int read(){ int x = 0,f = 1; char ch = getchar(); while(ch < '0'||ch > '9'){if(ch == '-')f=-1;ch = getchar();} while(ch >= '0'&&ch <= '9'){x = x * 10 + ch -'0';ch = getchar();} return x*f; } ////////////////////////////////////////////////////////////////// /* 算法:容斥原理 + 分塊 題目: 對於給出的n個詢問,每次求有多少個數對(x,y),滿足a≤x≤b,c≤y≤d, 且gcd(x,y) = k,gcd(x,y)函數為x和y的最大公約數。 1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000 */ const int MAXN = 50000 + 10; int tot; LL mu[MAXN+1],sum[MAXN+1],pri[MAXN+1]; bool mark[MAXN]; void get(){ mu[1] = 1; for(int i = 2;i <= MAXN;++i){ if(!mark[i])pri[tot++] = i,mu[i] = -1; for(int j = 0;j < tot&&i*pri[j] <= MAXN;++j){ mark[i*pri[j]] = 1; if(i % pri[j]==0){mu[i*pri[j]] = 0; break;} else mu[i*pri[j]] = -mu[i]; } } for(int i = 1;i <= MAXN;++i) //預處理前綴 sum[i] = sum[i-1] + mu[i]; } int cal(int n,int m){ if(n > m) swap(n,m); LL ans = 0,pos; for(LL i = 1;i <= n;i = pos + 1){ pos = min(n/(n/i),m/(m/i)); //分塊 ans += (sum[pos] - sum[i-1]) * (n/i) * (m/i); } return ans; } int main() { get(); int T = read(); while(T--){ int a = read(),b = read(),c = read(),d = read(),k = read(); LL ans = cal(b/k,d/k); ans -= cal((a-1)/k,d/k); ans -= cal(b/k,(c-1)/k); ans += cal((a-1)/k,(c-1)/k); printf("%lld\n",ans); } return 0; }
紅黑樹的定義: 一棵二叉查找樹如果滿足下面的紅黑性質,
【入門】匈牙利算法+HNOI2006 hero超級英雄題解,
zeromq學習記錄(一)最初的簡單示例使用ZMQ_REQ
題目如下: Problem D: Hart
第十一題 題目: 求二叉樹中節點的最大距離... 如果
HDU - 5047 Sawtooth Proble