鹤壁做网站公司哪家好,深圳做网站和视频宣传机构,校际凡科平台怎么登录,深圳市建设(集团)有限公司是国企吗Visible Trees HDU - 2841
题意#xff1a;
大概就是有个m*n个点的矩形从(1,1)到(m,n)#xff0c;问从(0,0)出发直线看过去最多能看到几个点。
题解#xff1a;
容斥做法参考 这个题和AcWing 201. 可见的点一样的#xff0c;但是这里介绍不同的做法#xff0c;用容斥做…Visible Trees HDU - 2841
题意
大概就是有个m*n个点的矩形从(1,1)到(m,n)问从(0,0)出发直线看过去最多能看到几个点。
题解
容斥做法参考 这个题和AcWing 201. 可见的点一样的但是这里介绍不同的做法用容斥做 不难知道我们要找的是区间[1,m]和[1,n]之间互质的对数(具体原因可以看上面的链接) 那我们可以这样做
选取一个区间[1,n],枚举n里面的数i然后对于每个数i我们看他在区间[1,m]中能找到多少互质的数对于枚举的每个i我们可以用容斥原理将i进行质因子分解这样得到cnt个互不相同质因子我们设AiA_{i}Ai代表被i的质因子pjp_{j}pj或pjp_{j}pj的幂次整除。 根据奇加偶减有奇数个素因子的数加偶数个的减得到在1~m区间中与x不互质的个数用n减掉就是答案
代码
#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);while(t--){int n,m;read(n,m);if(nm)swap(n,m);ll ans0;for(int i1;in;i){divide(i);anssolve(m);}coutansendl;}return 0;//Time_test();
}
