GCD Array
Time Limit: 11000/5500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 843 Accepted Submission(s):
205
function can be reduced to the following problem:
Maintain an array a
with index from 1 to l. There are two kinds of operations:
1. Add v to
ax for every x that gcd(x,n)=d.
2. Query
0".
For each test case, the first line contains two integers
l,Q(1<=l,Q<=5*10^4), indicating the length of the array and the number of
the operations.
In following Q lines, each line indicates an operation,
and the format is "1 n d v" or "2 x"
(1<=n,d,v<=2*10^5,1<=x<=l).
case number counting from 1.
Then output the answer to each query.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef __int64 LL; const int maxn = +;
const int INF = 2e5+;
LL p[maxn];
bool s[INF];
int prime[],len; void Init()
{
len = ;
memset(s,false,sizeof(s));
for(int i=;i<INF;i++)
{
if(s[i]==true)continue;
prime[++len] = i;
for(int j=i+i;j<INF;j=j+i)
s[j]=true;
}
}
void add(int x,int n,int num1)
{
for(int i=x;i<=n;i=i+(i&(-i)))
p[i] = p[i] + num1;
}
LL query(int x)
{
if(x==)return ;
LL sum1 = ;
while(x)
{
sum1=sum1+p[x];
x=x-(x&(-x));
}
return sum1;
}
int Q[],yz[],ylen,qlen;
void init(int n)
{
ylen = qlen = ;
for(int i=;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==)
{
while(n%prime[i]==) n=n/prime[i];
yz[++ylen] = prime[i];
}
}
if(n!=) yz[++ylen] = n;
Q[]=-;
for(int i=;i<=ylen;i++)
{
int k = qlen;
for(int j=;j<=k;j++)
Q[++qlen] = -*Q[j]*yz[i];
}
}
int main()
{
int n,m,hxl,d,v,size1,x,T=;
Init();
while(scanf("%d%d",&n,&m)>)
{
if(n==&&m==)break;
memset(p,,sizeof(p));
printf("Case #%d:\n",++T);
while(m--)
{
scanf("%d",&size1);
if(size1==)
{
scanf("%d%d%d",&hxl,&d,&v);
if(hxl%d!=)continue;
hxl = hxl /d;
int tom = n/d;
add(d,n,v);
init(hxl);
for(int i=;i<=qlen;i++)
if(Q[i]<) {
Q[i] = -Q[i];
if(Q[i]>tom)continue;
add(Q[i]*d,n,v);
}
else {
if(Q[i]>tom)continue;
add(Q[i]*d,n,-v);
}
}
else{
scanf("%d",&x);
LL sum1 = ;
for(int i=,la=;i<=x;i=la+){
la = x/(x/i);
sum1 = sum1 + (query(la)-query(i-))*(x/i);
}
printf("%I64d\n",sum1);
}
}
}
return ;
}
HDU 4947 GCD Array 容斥原理+树状数组的更多相关文章
-
HDU 4777 Rabbit Kingdom --容斥原理+树状数组
题意: 给一个数的序列,询问一些区间,问区间内与区间其他所有的数都互质的数有多少个. 解法: 直接搞有点难, 所谓正难则反,我们求区间内与其他随便某个数不互质的数有多少个,然后区间长度减去它就是答案了 ...
-
HDU 5862 Counting Intersections(离散化+树状数组)
HDU 5862 Counting Intersections(离散化+树状数组) 题目链接http://acm.split.hdu.edu.cn/showproblem.php?pid=5862 D ...
-
hdu 5517 Triple(二维树状数组)
Triple Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Sub ...
-
HDU 5869 Different GCD Subarray Query (GCD种类预处理+树状数组维护)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5869 问你l~r之间的连续序列的gcd种类. 首先固定右端点,预处理gcd不同尽量靠右的位置(此时gc ...
-
HDU 5869 Different GCD Subarray Query 树状数组+离线
Problem Description This is a simple problem. The teacher gives Bob a list of problems about GCD (Gr ...
-
HDU 5869 Different GCD Subarray Query 树状数组 + 一些数学背景
http://acm.hdu.edu.cn/showproblem.php?pid=5869 题意:给定一个数组,然后给出若干个询问,询问[L, R]中,有多少个子数组的gcd是不同的. 就是[L, ...
-
HDU 5792 L - World is Exploding 。容斥原理 + 树状数组 + 离散化
题目,要求找出有多少对这样的东西,四个数,并且满足num[a]<num[b] &&num[c]>num[d] 要做这题,首先要懂得用树状数组,我设,下面的小于和大于都是严格 ...
-
HDU 1394 Minimum Inversion Number ( 树状数组求逆序数 )
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394 Minimum Inversion Number ...
-
HDU 5862 Counting Intersections (树状数组)
Counting Intersections 题目链接: http://acm.split.hdu.edu.cn/showproblem.php?pid=5862 Description Given ...
随机推荐
-
Maven-3.2.2安装配置
(1)安装JDK,这里是1.7.0_51 (2)Maven-3.2.2下载地址:http://mirrors.cnnic.cn/apache/maven/maven-3/3.2.2/binaries/ ...
-
C++Builder 笔记
1.界面窗口如何不显示标题栏? 在Form属性栏里面把BorderStyle的值设为None 2.wchar_t wchar_t是C/C++的字符类型,是一种扩展的存储方式,wchar_t类型主要用在 ...
-
C# 条码标签打印程序,RDLC报表动态显示多条码标签的方法
初学c#,因最近公司客户要求原出货标签需实现条码化,练手的机会来了,遂动手做这个程序,开始都是一些增删改查操作一直很顺利,但到RDLC报表将条码显示到报表上犯难了,因为初学未接触过报表,上网查资料均一 ...
-
yii2源码学习笔记(十八)
View继承了component,用于渲染视图文件:yii2\base\View.php <?php /** * @link http://www.yiiframework.com/ * @co ...
-
poj1691绘画板
1 7 0 0 2 2 1 0 2 1 6 2 2 0 4 2 1 1 2 4 4 2 1 4 3 6 1 4 0 6 4 1 3 4 6 6 2 #include<stdio.h> #i ...
-
Linux 从 sar 到 sar2html 的认识
这些变形的工具.诸如:淘宝的Tsar.ksar.sar2html....等.都是通过抓取 sar的数据 所以在最终呈现的数据上变化不大.只是展现的手段和效果不一样而已 sar 是帮助我们 ...
-
hdu_3001_Travelling(状压DP)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3001 题意:给你N个点,M条边,每个点最多走两次,问走完N个点最短的路程为多少. 题解:注意这题有重边 ...
-
发布一个参考ssdb,用go实现的类似redis的高性能nosql:ledisdb
起因 ledisdb是一个参考ssdb,采用go实现,底层基于leveldb,类似redis的高性能nosql数据库,提供了kv,list,hash以及zset数据结构的支持. 我们现在的应用极大的依 ...
-
loadrunner代理录制脚本
1.打开loadrunner录制脚本选项: 2.start recording弹窗选择options: 3.设置loadrunner端口,可自定义:后面的浏览器设置代理需要用到此处设置的端口号: 4 ...
-
JavaScript开发工具简明历史
译者按: JavaScript开发要用到的工具越来越多,越来越复杂,为什么呢?你真的弄明白了吗? 原文: Modern JavaScript Explained For Dinosaurs 为了保证可 ...