提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

HDU 4407 Sum

HDU sum
2023-09-11 14:15:28 时间

Sum

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 4407
64-bit integer IO format: %I64d      Java class name: Main
XXX is puzzled with the question below: 

$1, 2, 3, ..., n (1\leq n\leq 400000)$ are placed in a line. There are $m (1\leq m\leq 1000) $operations of two kinds.

Operation 1: among the x-th number to the y-th number (inclusive), get the sum of the numbers which are co-prime with $p( 1\leq p\leq 400000)$.
Operation 2: change the x-th number to $c( 1\leq c\leq 400000)$.

For each operation, XXX will spend a lot of time to treat it. So he wants to ask you to help him.
 

Input

There are several test cases.
The first line in the input is an integer indicating the number of test cases.
For each case, the first line begins with two integers --- the above mentioned n and m.
Each the following m lines contains an operation.
Operation 1 is in this format: "1 x y p". 
Operation 2 is in this format: "2 x c".
 

Output

For each operation 1, output a single integer in one line representing the result.
 

Sample Input

1
3 3
2 2 3
1 1 3 4
1 2 3 6

Sample Output

7
0

Source

2012 ACM/ICPC Asia Regional Jinhua Online
 
解题：容斥原理暴力算出原解，然后暴力修改
赞
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 100;
 5 int pm[maxn],tot;
 6 unordered_map<int,int>ump;
 7 void init(LL x){
 8     tot = 0;
 9     for(int i = 2; i*i <= x; ++i){
10         if(x%i == 0){
11             pm[tot++] = i;
12             while(x%i == 0) x /= i;
13         }
14     }
15     if(x > 1) pm[tot++] = x;
16 }
17 LL solve(LL x,LL p){
18     LL ret = (x*(x + 1))>>1;
19     init(p);
20     for(int i = 1; i < (1<<tot); ++i){
21         int cnt = 0;
22         LL tmp = 1;
23         for(int j = 0; j < tot; ++j){
24             if((i>>j)&1){
25                 ++cnt;
26                 tmp *= pm[j];
27             }
28         }
29         LL y = x/tmp;
30         if(cnt&1) ret -= ((y*(y + 1))>>1)*tmp;
31         else ret += ((y*(y + 1))>>1)*tmp;
32     }
33     return ret;
34 }
35 int main(){
36     int kase,n,m,op,x,y,p;
37     scanf("%d",&kase);
38     while(kase--){
39         ump.clear();
40         scanf("%d%d",&n,&m);
41         for(int i = 0; i < m; ++i){
42             scanf("%d",&op);
43             if(op == 2){
44                 scanf("%d%d",&x,&y);
45                 ump[x] = y;
46             }else{
47                 scanf("%d%d%d",&x,&y,&p);
48                 LL ret = solve(y,p) - solve(x-1,p);
49                 for(auto &it:ump){
50                     if(it.first >= x && it.first <= y){
51                         if(__gcd(it.first,p) == 1) ret -= it.first;
52                         if(__gcd(it.second,p) == 1) ret += it.second;
53                     }
54                 }
55                 printf("%I64d\n",ret);
56             }
57         }
58     }
59     return 0;
60 }
View Code

 

相关文章