如何使用BIT解决此问题？

Question

我发现一个很好的数学问题，但我仍然无法解决它，我试图找到一个解决方案，使用谷歌，发现它可以解决使用二进制索引树数据结构，但解决方案并不清楚。

这里称为查找魔术三胞胎的问题，它可以在UVA线上解题系统中找到：

（A + B^2）模k = C^3模k，其中一个< = B < = c和1 < = a，b，c < = n。

给定n和k（1 < = n，k < = 10^5），对于已知的n和k值存在多少个不同的魔术三元组。如果三个值中的任何一个在三个中都不相同，则三元组与另一个不同。

，并在这里，我找到了解决办法：

#include <cstdio> 
#include <cstring> 
using namespace std; 

typedef long long int64; 

const int MAX_K = (int)(1e5); 

int N, K; 

struct BinaryIndexedTree{ 

    typedef int64 bit_t; 

    static const int MAX_BIT = 3*MAX_K + 1; 
    bit_t data[MAX_BIT+1]; 
    int SIZE; 

    void init(int size){ 
     memset(data, 0, sizeof(data)); 
     SIZE = size; 
    } 

    bit_t sum(int n){ 
     bit_t ret = 0; 
     for(;n;n-=n&-n){ 
      ret += data[n]; 
     } 
     return ret; 
    } 

    bit_t sum(int from, int to){ 
     return sum(to)-sum(from); 
    } 

    void add(int n, bit_t x){ 
     for(n++;n<=SIZE;n+=n&-n){ 
      data[n]+=x; 
     } 
    } 
}; 

BinaryIndexedTree bitree; 


void init(){ 
    scanf("%d%d", &N, &K); 
} 

int64 solve(){ 
    bitree.init(2*K+1); 

    int64 ans = 0; 
    for(int64 i=N; i>=1; i--){ 
     int64 b = i * i % K, c = i * i * i % K; 
     bitree.add(c, 1); 
     bitree.add(c+K, 1); 
     bitree.add(c+2*K, 1); 
     int64 len = i; 
     if(len >= K){ 
      ans += (len/K) * bitree.sum(K); 
      len %= K; 
     } 
     if(len > 0){ 
      ans += bitree.sum(b + 1, b + len + 1); 
     } 
    } 

    return ans; 
} 

int main(){ 
    int T; 
    scanf("%d", &T); 
    for(int i=0; i<T; i++){ 
     init(); 
     printf("Case %d: %lld\n", i+1, solve()); 
    } 

    return 0; 
} 

Answer 1

你决心使用BITS？我会认为普通的数组会这样做。我首先创建三个大小为k的数组，其中arrayA [i] =范围内的值的数量等于i mod k，arrayB [i] =在范围中的b值的数量，其中b^2 = i mod k和arrayC [i] = c的值的数量，其中c^3 = i mod k。 N和k都是< = 10^5，所以您可以依次考虑a的每个值，反过来依次考虑c，然后依次考虑c，但如果k比n小得多，则可以更清楚，因为它们会是某种fiddly fence-post counting表达式，允许你计算0..n范围内有多少数字等于每个i的i mod k。

给定那三个数组，然后考虑每个可能的数字对i，j，其中0 < = i，j < k并且计算出具有这些值mod k的arrayA [i] * arrayB [j]对。在arrayAB [i + j mod k]中求和这些以找出可以选择a + b^2 mod k = x的方式的数量，其中0 < = x < k。现在你有两个数组arrayAB和arrayC，其中arrayAB [i] * arrayC [i]是找到一个三元组的方法的数量，其中a + b^2 = c^3] = i，所以总和为0 < =我< k得到你的答案。