首页 > HDU 4407 sum 容斥原理

HDU 4407 sum 容斥原理

算法:

利用数据1...N的性质，求与P的互质的个数，位运算，容斥定理。。

#include
#include
#include<string.h>
#include
#include
#include<string>
#include
#include
#include<set>
#include
using namespace std;struct info
{int s,e,p,num;
}seg[1010];struct pinfo
{int id, v, num;   
}p[1010];int factor[1000]; //保存因子 
map<int,int>mp;int gcd( int n, int m )
{return m ? gcd(m, n % m ) : n;    
}//容斥定理求互质之和 
long long cal( int x, int n)
{//分解出x的因子if( x == 0 )return 0;int i,Lim = sqrt( x * 1.0 ), cnt = 0;for( i = 2; i <= Lim; i++){if( x % i == 0 ){factor[++cnt] = i;while( x % i == 0 )x = x / i;   }        }if( x != 1 ){factor[++cnt] = x;      }int mask = 1 << cnt;long long ans = 0;for( int i = 1; i < mask; i++){  int tt = 0, fac = 1, k;for( int j = 0; j < cnt; j++){if( i & (1<<j) ){tt++;fac *=  factor[j+1];}       }//如果是奇数项      if( tt & 1 ){k = n / fac;ans += ( fac + 1LL * fac * k ) * k / 2;}   else{k = n / fac;ans -= ( fac + 1LL * fac * k ) * k / 2;  } }     return ans;   
}int main( )
{int N, M, a, b, c, d, c1, c2, T;scanf("%d",&T);while( T-- ){  scanf("%d%d",&N,&M);c1 = c2 = 0;for( int i = 1; i <= M; i++){scanf("%d",&a);if( a == 1 ){scanf("%d%d%d",&seg[c1].s, &seg[c1].e, &seg[c1].p);seg[c1].num = i;       c1++;}else{scanf("%d%d",&p[c2].id, &p[c2].v);p[c2].num = i;c2++; }              } long long x, y, pans;for( int i = 0; i < c1; i++) //枚举每一个查询 
     {x = cal(seg[i].p, seg[i].s-1);y = cal(seg[i].p, seg[i].e);pans = ((1 + seg[i].e * 1LL) * seg[i].e * 1LL / 2 - y ) - (1 + seg[i].s - 1 ) * 1LL * (seg[i].s - 1) * 1LL / 2 + x;mp.clear();for( int j = 0; j < c2; j++){if( p[j].num <  seg[i].num && seg[i].e >= p[j].id && seg[i].s <= p[j].id ){mp[p[j].id] = p[j].v;   }else if( p[j].num > seg[i].num )break;    }map<int,int>::iterator it;for( it = mp.begin(); it != mp.end(); it++){int xx = gcd(seg[i].p, it->second);int yy = gcd(seg[i].p, it->first);if( yy == 1 && xx != 1 )pans -= it->first;else if( yy != 1 && xx == 1 )pans += it->second;      else if( yy == 1 && xx == 1 )pans += it->second - it->first;  } printf("%I64d
", pans); }}return 0;
}

 

转载于:https://www.cnblogs.com/tangcong/archive/2012/09/22/2698434.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 相机标定 matlab opencv ROS三种方法标定步骤（2）

    #include #include #include #include #include #include #include

  • 剑指offer：面试题20. 表示数值的字符串

    题目：表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。 解题： 数值错误的形式有多种多样，但是正确的...

  • 数字太大了，计算加法、减法会报错，结果不正确？怎么办？用JavaScript实现大数据（超过20位的数字）相加减运算。

    加法伺候  //超过20位数值相加---------------------------------------- function bigNumAdd(a, b) {if (!(typeof a === "string" && typeof b === "string")) return console.log("传入参数必...

  • Python中使用中文正则表达式匹配指定的中文字符串

    业务场景： 从中文字句中匹配出指定的中文子字符串 .这样的情况我在工作中遇到非常多, 特梳理总结如下. 难点: 处理GBK和utf8之类的字符编码, 同时正则匹配Pattern中包含汉字,要汉字正常发挥作用,必须非常谨慎.推荐最好统一为utf8编码,如果不是这种最优情况,也有酌情处理. 往往一个具有普适性的正则表达式会简化程...

  • Linux 下获取本机所有网卡 以及 网卡对应ip 列表

    简单record 一下 #include // 'struct sockaddr_in' #include #include // 'struct ifreq' and 'struct if_nameindex' #include #inc...

©2024 11GX.COM