如何用php数据库做网站,培训机构咨询,网络推广运营推广,湖北金扬建设网站GCD HDU - 1695
题意#xff1a;
给出a,b,c,d,k,求出axb, cyd 且gcd(x,y) k 的#xff08;x,y#xff09;的对数。 求的是不同数量对的总数
题解#xff1a;
和这个题一样P3455 [POI2007]ZAP-Queries#xff0c;但是本题要求求不同数量对的总数…GCD HDU - 1695
题意
给出a,b,c,d,k,求出axb, cyd 且gcd(x,y) k 的x,y的对数。 求的是不同数量对的总数
题解
和这个题一样P3455 [POI2007]ZAP-Queries但是本题要求求不同数量对的总数所以最后的结果要减去重复值 如果是莫比乌斯分块做法对于区间[1,b],[1,d],bd,重复部分是[1,b]部分所以减去solve(b,b)/2 如果是容斥做法对于每个i∈[1,b],求[1,d]中互质的数量那我们减去i与[1,i]中互质的数量 详细看代码
代码
莫比乌斯分块
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e69;
int prime[maxn];
int mu[maxn];
int sum[maxn];
int vis[maxn];
int cnt0;
void get_mu(int N){mu[1]1;vis[1]vis[0]1;for(int i2;iN;i){if(!vis[i]){prime[cnt]i;mu[i]-1;}for(int j1;jcnti*prime[j]N;j){vis[i*prime[j]]1;if(i%prime[j]0)break;mu[i*prime[j]]-mu[i];}}for(int i1;iN;i){sum[i]sum[i-1]mu[i];}
}
ll solve(int a,int b,int k){a/k;b/k;int minnmin(a,b);ll ans0;for(int l1,r;lminn;lr1){rmin(a/(a/l),b/(b/l));ans1ll*(sum[r]-sum[l-1])*(a/l)*(b/l);}return ans;
}
int main()
{//rd_test();get_mu(1000000);int t;read(t);int cas0;while(t--){int a,b,c,d,k;read(a,b,c,d,k);if(k0){printf(Case %d: 0\n,cas);continue;}if(bd)swap(b,d);
// printf(%d %d %d %d\n,a,b,c,d); printf(Case %d: %lld\n,cas,solve(b,d,k)-solve(b,b,k)/2);}//Time_test();
}
容斥
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn3e59;
int prime[maxn];
int cnt0;
void divide(int n){cnt0;for(int i2;i*in;i){if(n%i0){prime[cnt]i;while(n%i0)n/i;}}if(n!1)prime[cnt]n;
}
int solve(int S){int ans0;for(int i1;i(1cnt);i){int tmp1;int num0;for(int j0;jcnt;j){if(i(1j)){tmp*prime[j];num;}}if(num1)ansS/tmp;else ans-S/tmp;}return S-ans;
}
int main()
{//rd_test();int t;read(t);int cas0;while(t--){int a,b,c,d,k;read(a,b,c,d,k);if(k0){printf(Case %d: 0\n,cas);continue;}if(bd)swap(b,d);b/k;d/k;ll ans0;for(int i1;ib;i){divide(i);anssolve(d)-solve(i-1);}printf(Case %d: %lld\n,cas,ans);}return 0;//Time_test();
}
