首页 > 代码库 > HDU 4947 GCD Array
HDU 4947 GCD Array
GCD Array
Time Limit: 11000/5500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 843 Accepted Submission(s): 205
Problem Description
Teacher Mai finds that many problems about arithmetic 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
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
Input
There are multiple test cases, terminated by a line "0 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).
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).
Output
For each case, output "Case #k:" first, where k is the case number counting from 1.
Then output the answer to each query.
Then output the answer to each query.
Sample Input
6 4
1 4 1 2
2 5
1 3 3 3
2 3
0 0
Sample Output
Case #1:
6
7
Author
xudyh
Source
2014 Multi-University Training Contest 8
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef __int64 LL; 7 8 const int maxn = 50000+3; 9 const int INF = 2e5+3; 10 LL p[maxn]; 11 bool s[INF]; 12 int prime[17985],len; 13 14 void Init() 15 { 16 len = 0; 17 memset(s,false,sizeof(s)); 18 for(int i=2;i<INF;i++) 19 { 20 if(s[i]==true)continue; 21 prime[++len] = i; 22 for(int j=i+i;j<INF;j=j+i) 23 s[j]=true; 24 } 25 } 26 void add(int x,int n,int num1) 27 { 28 for(int i=x;i<=n;i=i+(i&(-i))) 29 p[i] = p[i] + num1; 30 } 31 LL query(int x) 32 { 33 if(x==0)return 0; 34 LL sum1 = 0; 35 while(x) 36 { 37 sum1=sum1+p[x]; 38 x=x-(x&(-x)); 39 } 40 return sum1; 41 } 42 int Q[5003],yz[1000],ylen,qlen; 43 void init(int n) 44 { 45 ylen = qlen = 0; 46 for(int i=1;prime[i]*prime[i]<=n;i++) 47 { 48 if(n%prime[i]==0) 49 { 50 while(n%prime[i]==0) n=n/prime[i]; 51 yz[++ylen] = prime[i]; 52 } 53 } 54 if(n!=1) yz[++ylen] = n; 55 Q[0]=-1; 56 for(int i=1;i<=ylen;i++) 57 { 58 int k = qlen; 59 for(int j=0;j<=k;j++) 60 Q[++qlen] = -1*Q[j]*yz[i]; 61 } 62 } 63 int main() 64 { 65 int n,m,hxl,d,v,size1,x,T=0; 66 Init(); 67 while(scanf("%d%d",&n,&m)>0) 68 { 69 if(n==0&&m==0)break; 70 memset(p,0,sizeof(p)); 71 printf("Case #%d:\n",++T); 72 while(m--) 73 { 74 scanf("%d",&size1); 75 if(size1==1) 76 { 77 scanf("%d%d%d",&hxl,&d,&v); 78 if(hxl%d!=0)continue; 79 hxl = hxl /d; 80 int tom = n/d; 81 add(d,n,v); 82 init(hxl); 83 for(int i=1;i<=qlen;i++) 84 if(Q[i]<0) { 85 Q[i] = -Q[i]; 86 if(Q[i]>tom)continue; 87 add(Q[i]*d,n,v); 88 } 89 else { 90 if(Q[i]>tom)continue; 91 add(Q[i]*d,n,-v); 92 } 93 } 94 else{ 95 scanf("%d",&x); 96 LL sum1 = 0; 97 for(int i=1,la=0;i<=x;i=la+1){ 98 la = x/(x/i); 99 sum1 = sum1 + (query(la)-query(i-1))*(x/i);100 }101 printf("%I64d\n",sum1);102 }103 }104 }105 return 0;106 }
HDU 4947 GCD Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。