Educational Codeforces Round 24 E. Card Game Again[数论][线段树]-白红宇

Educational Codeforces Round 24 E. Card Game Again[数论][线段树]

阅读量：7063 次

发布时间：2019-06-28

本文共 2287 字，大约阅读时间需要 7 分钟。

题目：

题意：有多少种情况使得对数组剔除前缀x项和后缀y项后，中间的项乘积能被k整除

题解：直接记录区间乘积数字过大，利用取余的分配律 (a%x)*(b%x)==(a*b)%x，暴力枚举x，二分寻找最大的y，线段树保存区间取模值。

1 #define _CRT_SECURE_NO_DEPRECATE  2 #pragma comment(linker, "/STACK:102400000,102400000")  3 #include
     
          4 #include
      
           5 #include
       
            6 #include
        
           7 #include
         
              8 #include
          
            9 #include
           
             10 #include
            
              11 #include
             
               12 #include
              
                13 #include
               
                 14 #include
                
                  15 #include
                 
                   16 #include
                   17 #include
                   
                     18 #include
                    
                      19 #include
                     
                       20 #define pii pair
                      
                        21 #define mod 1000000007 22 #define mp make_pair 23 #define pi acos(-1) 24 #define eps 0.00000001 25 #define mst(a,i) memset(a,i,sizeof(a)) 26 #define all(n) n.begin(),n.end() 27 #define lson(x) ((x<<1)) 28 #define rson(x) ((x<<1)|1) 29 #define inf 0x3f3f3f3f 30 typedef long long ll; 31 typedef unsigned long long ull; 32 using namespace std; 33 34 const int maxn = 1e5 + 5; 35 int ori[maxn]; 36 ll md; 37 class t { 38 public: 39 int l, r; 40 ll value; 41 t() { l = 0, r = 0; } 42 }tree[maxn * 4 + 5]; 43 44 void build(int l, int r, int u) 45 { 46 tree[u].l = l; 47 tree[u].r = r; 48 if (l == r) 49 { 50 tree[u].value = ori[l] % md; 51 return; 52 } 53 int mid = (l + r) >> 1; 54 build(l, mid, lson(u)); 55 build(mid + 1, r, rson(u)); 56 tree[u].value = (tree[lson(u)].value* tree[rson(u)].value) % md; 57 } 58 59 ll query(int l, int r, int u) 60 { 61 if (l > r)return 0; 62 if (tree[u].l >= l&&tree[u].r <= r)return tree[u].value; 63 int mid = (tree[u].l + tree[u].r) >> 1; 64 ll ret = 1; 65 if (l <= mid)ret *= query(l, r, lson(u)); 66 if (r > mid)ret *= query(l, r, rson(u)); 67 return ret%md; 68 } 69 70 inline ll check(int l, int r) 71 { 72 return query(l, r, 1); 73 } 74 75 int main() 76 { 77 ios::sync_with_stdio(false); 78 cin.tie(0); cout.tie(0); 79 int i, j, k, m, n; 80 cin >> n >> md; 81 for (int i = 1; i <= n; ++i) 82 cin >> ori[i]; 83 build(1, n, 1); 84 ll ans = 0; 85 86 for (int i = 1; i <= n; ++i) 87 { 88 int l = i, r = n; 89 while (r - l > 1) 90 { 91 int mid = (l + r) >> 1; 92 if (check(i, mid))l = mid; 93 else r = mid; 94 } 95 if (!check(i, l)) 96 ans += n - l + 1; 97 else if(!check(i, r)) ans += n - r + 1; 98 } 99 cout << ans;100 return 0;101 }