Nico NumberTime Limit:2 Seconds Memory Limit:262144 KB
Kousaka HonokaandMinami Kotoriare playing a game about a secret ofYazawa Nico.
When the game starts,Kousaka Honokawill giveMinami Kotorian arrayAofNnon-negative integers. There is a special kind of number in the array, which is calledNicoNico-number. We call a integerxis aNicoNico-number, if all integers(no more thanx) that is coprime withxcould form an Arithmetic Sequence.ThenMinami Kotoriwill choose some consecutive part of the arrayA, wondering the number ofNicoNico-numberin this part. What’s more,Kousaka Honokasometimes modify the value of some consecutive elements in the array. Now it is your task to simulate this game!Input
There are multiple test cases in input, you should process to the end of file.
For each case, the first line is an integerN, the number of elements in the array described above. Then second line containsNintegers no greater than 107, the elements of the array initially.(1 <= N <= 100,000)
The third line is a integerT, the number of the operations of the game. Each line of the followingTlines is in one of the following formats.(1 <= T <= 100,000)
"1 L R" :Minami Kotoriwill chooses the consecutive part of the array from theLth toRth element inclusive. (1 <=L <= R<= N)
"2 L R v" :Kousaka Honokawill change the value of thepth elementA[p]in the array toA[p]%vfor allL <= p <= R.(1 <= L <= R <= N, 1 <= v <= 107)
"3 p x" :Kousaka Honokawill change the value of thepth elementA[p]tox.(1 <= p <= N, 1 <= x <= 107)
Output
Each time whenMinami Kotorichooses some part of the array, you should output a line, the number ofNicoNico-numberin that part.
Sample Input34 6 961 1 31 3 32 1 1 101 1 33 2 41 1 3Sample Output2022Hint
4 is aNicoNico-numberbecause only 1 and 3 is coprime with 4 among the integers no greater than 4, and could form an Arithmetic Sequence {1,3}.
题目大意：定义一个NicoNico-number，如果x是NicoNico-number，那么所有小于x的且与x互质的整数是一个等差数列，初始给出n个数字的数组，三种操作：
1 l r 问在[l,r]内有多少个NicoNico-number数
2 l r v 对于[l,r]内的数全部对v取余
3 k x 将第k个数换为x
对每一次询问做出输出。
1、首先写一个找规律的，，发现NicoNico-number是有三种组成的第一种是素数，第二种是2的x次幂，第三种是6
2、那么可以建一个数组，直接标记某个数是不是NicoNico-number
3、使用线段树维护一段区间的NicoNico-number个数，然后可以进行对某一个数的修改，和对一个区间的查询。
对于第二种操作。我们要知道对于一个数x取余操作，最多会执行log(x)次，因为每次取余至少数值会减少一半，所以对于每个数来说最多会有log(x)次操作，之后会因为v大于当前值，而不用执行操作。既然取余的次数不多，那么就可以对区域操作进行暴力，维护一段区间的最大值，如果最大值小于v，那么这一段不用更新，否则就遍历的最低层进行取余。
4、对于n个数来说，查找到一个数需要log(n)，一个数最多会被修改log(x)次，所以总的时间不会超过n*log(n)*log(x)。
#include <cstdio>#include <cstring>#include <queue>#include <set>#include <vector>#include <cmath>#include <map>#include <stack>#include <algorithm>using namespace std ;#define LL __int64#define INF 0x3f3f3f3f#define PI acos(-1.0)#define root 1,n,1#define int_rt int l,int r,int rt#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1const int mod = 1e9+7 ;const double eqs = 1e-9 ;int cl[400000] , num[400000] ;int a[10000005] , check[10000005] ;int tot ;void init() {memset(check,-1,sizeof(check)) ;tot = 0 ;for(int i = 2 ; i <= 10000000 ; i++) {if( check[i] == -1 ){a[tot++] = i ;check[i] = 1 ;}for(int j = 0 ; j < tot ; j++) {if( i*a[j] >= 10000000 ) break ;check[i*a[j]] = 0 ;if( i%a[j] == 0 ) break ;}}check[0] = check[1] = check[6] = 1 ;for(int i = 2 ; i <= 10000000 ; i *= 2)check[i] = 1 ;}void push_up(int rt) {cl[rt] = max(cl[rt<<1],cl[rt<<1|1]) ;num[rt] = num[rt<<1]+num[rt<<1|1] ;}void create(int_rt) {cl[rt] = num[rt] = 0 ;if( l == r ) {scanf("%d", &cl[rt]) ;if( check[ cl[rt] ] == 1 ) num[rt] = 1 ;return ;}create(lson) ;create(rson) ;push_up(rt) ;}void update1(int ll,int rr,int v,int_rt) {if( ll > r || rr < l ) return ;if( cl[rt] < v ) return ;if( l == r ) {cl[rt] %= v ;if( check[ cl[rt] ] == 1 ) num[rt] = 1 ;else num[rt] = 0 ;return ;}update1(ll,rr,v,lson) ;update1(ll,rr,v,rson) ;push_up(rt) ;}void update2(int k,int x,int_rt) {if( l == r && l == k ) {cl[rt] = x ;if( check[ cl[rt] ] == 1 ) num[rt] = 1 ;else num[rt] = 0 ;return ;}int mid = (l+r)/2 ;if(k <= mid) update2(k,x,lson) ;else update2(k,x,rson) ;push_up(rt) ;}int query(int ll,int rr,int_rt) {if( ll > r || rr < l ) return 0 ;if( ll <= l && rr >= r ) return num[rt] ;return query(ll,rr,lson) + query(ll,rr,rson) ;}int main() {int n , m , i , k , l , r , v , x ;init() ;while( scanf("%d", &n) !=EOF ) {create(root) ;scanf("%d", &m) ;while( m– ) {scanf("%d", &k) ;if( k == 1 ) {scanf("%d %d", &l, &r) ;printf("%d\n", query(l,r,root)) ;}else if( k == 2 ) {scanf("%d %d %d", &l, &r, &v) ;update1(l,r,v,root) ;}else {scanf("%d %d", &i, &x) ;update2(i,x,root) ;}}}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
而更像是听见了天地间冥冥中的呼唤，
