首页 > 代码库 > hdu 4407 Sum

hdu 4407 Sum

2024-08-03 16:19:38   213人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4407

题意：给定初始n个数1..n，两个操作，①1 x y p  询问第x个数到第y个数中与p互质的数的和; ②：2 x y  把第x个数变成y；

思路：

把p分解质因子，然后找出(1,pos)内与p不互质的，然后用的减去就是互质的和，第二个操作用到map映射，记录在那个位置改变之后的数。

  1 #include <cstdio>  2 #include <cstring>  3 #include <map>  4 #include <vector>  5 #include <algorithm>  6 #define LL __int64  7 #define maxn 400001  8 using namespace std;  9  10 int t; 11 int n,m; 12  13 LL gcd(LL a,LL b) 14 { 15     return b==0?a:gcd(b,a%b); 16 } 17  18  19 LL deal(LL x,LL y) 20 { 21     LL res=x*(x+1)/2; 22     vector<int>p; 23     for(int i=2; i*i<=y; i++) 24     { 25         if(y%i==0) 26         { 27             p.push_back(i); 28             while(y%i==0) 29             { 30                 y/=i; 31             } 32         } 33     } 34     if(y>1) p.push_back(y); 35     LL ans=0; 36     for(int i=1; i<(1<<((int)p.size())); i++) 37     { 38         LL xx=0; 39         LL c=1; 40         for(int j=0; j<(int)p.size(); j++) 41         { 42             if(i&(1<<j)) 43             { 44                 xx++; 45                 c*=p[j]; 46             } 47         } 48         LL t=x/c; 49         LL sum=((t+1)*t/2)*c; 50         if(xx%2) 51         { 52             ans+=sum; 53         } 54         else 55             ans-=sum; 56     } 57     return res-ans; 58 } 59  60 int main() 61 { 62     map<int,int>q; 63     scanf("%d",&t); 64     while(t--) 65     { 66         q.clear(); 67         scanf("%d%d",&n,&m); 68         int x,y,op,pp; 69         for(int i=1; i<=m; i++) 70         { 71             scanf("%d",&op); 72             if(op==1) 73             { 74                 scanf("%d%d%d",&x,&y,&pp); 75                 LL sum=deal((LL)y,(LL)pp)-deal((LL)(x-1),(LL)pp); 76                 map<int,int>::iterator it=q.begin(); 77                 while(it!=q.end()) 78                 { 79                     if(it->first>=x&&it->first<=y) 80                     { 81                         if(gcd(it->first,pp)==1) 82                         { 83                             sum-=it->first; 84                         } 85                         if(gcd(it->second,pp)==1) 86                         { 87                             sum+=it->second; 88                         } 89                     } 90                     it++; 91                 } 92                 printf("%I64d\n",sum); 93             } 94             else 95             { 96                 scanf("%d%d",&x,&y); 97                 q[x]=y; 98             } 99         }100     }101     return 0;102 }
View Code

 

hdu 4407 Sum


联系
我们