如何使用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得到你的答案。