1,[POI2007]ZAP-Queries

~~~题面~~~
题解: 首先列出式子:$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$
    $$[gcd(i, j) == d] = [gcd(\lfloor{\frac{i}{d}}\rfloor,\lfloor{\frac{j}{d}}\rfloor) == 1]$$
    所以原式 $$\Rightarrow \quad \sum_{i = 1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j = 1}^{\lfloor{\frac{m}{d}}\rfloor}[gcd(i, j)==1]$$
    $$\Rightarrow \quad \sum_{i = 1}^{n}\sum_{j = 1}^{m}\sum_{d|gcd(i, j)}\mu(d)$$
    因为$\mu(d)$会被统计到当且仅当$d | i \quad and \quad d | j$,即$d | gcd(i, j)$
    那么考虑将满足条件的i和j两两搭配,组成的方案数就是$\mu(d)$会被统计到的次数,
    也就是$\mu(d)$会被统计到$\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$次
    $$\Rightarrow \quad ans=\sum_{i=1}^{min(n,m)}{\mu(d)\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor}$$
    然后观察到$\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$中有很多小段$\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$乘积是固定的,也就是$\lfloor{\frac{n}{d}}\rfloor$和$\lfloor{\frac{m}{d}}\rfloor$同时为一个固定的值,因此我们可以用整数分块优化

 #include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 55000
int t, n, m, d;
int prime[AC], mu[AC], sum[AC], tot;
bool z[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} void getprime()
{
int now;
mu[] = ;
for(R i = ; i <= ; i++)
{
if(!z[i]) prime[++tot] = i, mu[i] = -;
for(R j = ; j <= tot; j++)
{
now = prime[j];
if(now * i > ) break;
// printf("!!!%d %d\n", now, i);
z[now * i] = true;
if(!(i % now)) break;
mu[i * now] = -mu[i];
}
}
for(R i = ; i <= ; i++)
sum[i] = mu[i] + sum[i - ];
} int ans; void work()
{
int pos;
t = read();
for(R i = ; i <= t; i++)
{
n = read(), m = read(), d = read();
n /= d, m /= d;
int b = min(n, m);
ans = ;
for(R j = ; j <= b; j = pos + )
{
pos = min(n / (n / j), m / (m / j));
ans += (sum[pos] - sum[j-]) * (n / j) * (m / j);
}
printf("%d\n", ans);
}
} int main()
{
// freopen("in.in", "r", stdin);
getprime();
work();
// fclose(stdin);
return ;
}

2,[HAOI2011]Problem b

~~~题面~~~
题解: 这题相比上题多出了两个限制条件,同时对上下限都有限制,那么此时可以用一个容斥来求。
    设$cal(n,m)$表示满足$x \le n$和$y \le m$且$gcd(x, y) = d$的点对个数,
    那么$$ans = cal(b, d) - cal(a - 1, d) - cal(b, c - 1) + cal(a - 1, c - 1);$$

 #include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 55000
#define LL long long
int a, b, c, d, tot, k, t, ans;
int prime[AC], mu[AC], sum[AC];
bool z[AC]; inline int read()
{
int x = ; char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} void pre()
{
int now;
mu[] = ;
for(R i = ; i <= ; i++)
{
if(!z[i]) prime[++tot] = i, mu[i] = -;//质数的mu值肯定都是-1
for(R j = ; j <= tot; j++)
{
now = prime[j];
if(now * i > ) break;
z[now * i] = true;
if(!(i % now)) break;
mu[i * now] = -mu[i];//error这里的mu是由mu[i]得来的啊!!!
}
}
for(R i = ; i <= ; i++) sum[i] = sum[i - ] + mu[i];
} int cal(int n, int m)
{
n /= k, m /= k;
int b = min(n, m), pos, rnt = ;
for(R i = ; i <= b; i = pos + )
{
pos = min(n / (n / i), m / (m / i));
rnt += (sum[pos] - sum[i-]) * (n / i) * (m / i);
}
return rnt;
}
//ans = cal(b, d) - cal(a - 1, d) - cal(b, c - 1) + cal(a - 1 , c - 1),相当于容斥 void work()
{
t = read();
for(R i = ; i <= t; i++)
{
a = read(), b = read(), c = read(), d = read(), k = read();
ans = cal(b, d) - cal(a - , d) - cal(b, c - ) + cal(a - , c - );
printf("%d\n", ans);
}
} int main()
{
// freopen("in.in", "r", stdin);
pre();
work();
// fclose(stdin);
return ;
}

最新文章

  1. JS学习:第二周——NO.4DOM库
  2. Leetcode: Validate IP Address
  3. PHP从数据库导出EXCEL文件
  4. Debian下安装Firefox与flash简介
  5. 金融证券协议FIX/FAST/STEP
  6. SQLserver的存储过程
  7. oracle11g密码大小写敏感问题
  8. Linux之sed详解
  9. C++实现发送HTTP请求
  10. STL中序列式容器的共性
  11. 02-Go语言数据类型与变量
  12. 【Tools】Pycharm 2018专业版 linux安装教程 附2018专业版密钥
  13. extend与append的区别
  14. 如何获取ubuntu源码包里面的源码?
  15. 第15课 右值引用(2)_std::move和移动语义
  16. 收藏点webservice接口
  17. Shell教程 之传递参数
  18. OneZero第二次站立会议(2016.3.22)
  19. P1280 尼克的任务 线性DP
  20. nodejs的package.json

热门文章

  1. Kafka在高并发的情况下,如何避免消息丢失和消息重复?kafka消费怎么保证数据消费一次?数据的一致性和统一性?数据的完整性?
  2. (转)Html邮件CSS指南
  3. Oracle DELETE和TRUNCATE 的区别
  4. Consul初体验
  5. VMware SDK使用指南
  6. 【system.file】使用说明
  7. Bootstrap框架(图标)
  8. Python3 Tkinter-Toplevel
  9. Python3 Tkinter-Checkbutton
  10. es6从零学习(四):Class的继承