Showing posts with label Spoj. Show all posts
Showing posts with label Spoj. Show all posts
FACT0 - Integer Factorization (15 digits)
FACT0 - Integer Factorization (15 digits)
টপিকঃ প্রাইম ফ্যাক্টর
হিন্টঃ সিভ দিয়ে করলে টাইম লিমিট, নরমালি করতে হবে। প্রথমে x = ২ দিয়ে যতবার যায় ভাগ তারপর ৩ দিয়ে , এরপর ৫ দিয়ে...
যখন x*x >N হয়ে যাবে তখন লুপটা ব্রেক হবে।
এরপর শেষে সংখ্যাটি ১ এর চেয়ে বড় থাকলে ওইটা একটা প্রাইম নাম্বার হবে, আর প্রতিবার ভাগ করার সময় একটা কাউন্ট রাখবো যেইটা দ্বারা বুঝবো ওইটা ওই প্রাইম ডিভিজর এর কাউন্ট।😀
কোডঃ
SUBXOR - SubXor
SUBXOR - SubXor
Subarray Xor
Topic: Trie Tree
Explanation
Solution 01:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 200005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; struct trie { int L,R; int lft, rgt; trie(){ L = R = 0; lft = rgt = -1; } }; int Index = 0; void Insert(int value, int idx, int depth, trie *tree) { for(int i = depth-1; i >= 0; i--){ int bit = (value >> i ) & 1; if(bit){ tree[idx].R++; if(tree[idx].rgt == -1){ tree[idx].rgt = ++Index; idx = Index; } else idx = tree[idx].rgt; } else{ tree[idx].L++; if(tree[idx].lft == -1){ tree[idx].lft = ++Index; idx = Index; } else idx = tree[idx].lft; } } } int Query(int value, int cmp, int idx, int depth, trie* tree) { int ans = 0; for(int i = depth-1; i >= 0; i--){ int vBit = (value >>i) & 1; int cBit = (cmp >> i) & 1; if(cBit){ if(vBit){ ans += tree[idx].R; idx = tree[idx].lft; } else{ ans += tree[idx].L; idx = tree[idx].rgt; } } else{ if(vBit) idx = tree[idx].rgt; else idx = tree[idx].lft; } if(idx == -1)break; } return ans; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int T; cin >> T; while(T--){ trie tree[MAX]; Index = 0; int n,k; cin >> n >> k; int XOR = 0; ll ans = 0; Insert(0,0,20,tree); for(int i =0; i < n; i++){ int x; cin >> x; XOR = XOR ^ x; ans += Query(XOR,k,0,20,tree); Insert(XOR,0,20,tree); } cout << ans << endl; } //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |