Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and Gcd Queries CodeChef Solution
Problem -Chef and Gcd Queries CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Chef and Gcd Queries CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
///template<typename T> using ordermultiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
///(X).order_of_key(value) /// return lower_bound(value)
///(*X).find_by_order(index) /// return value (0 index)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /// mt19937_64 (long long)
auto my_rand(long long l,long long r)
{
return uniform_int_distribution<long long>(l,r)(rng);
}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> psi;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;
typedef vector<string> vss;
const int N = 100001;
const int M = 20;
const int MOD = 1000000007;
const int Mod = 998244353;
const int inf = 1234567890;
const ll INF = 1122334455667788990;
#define fast() ios_base::sync_with_stdio(false),cin.tie(NULL)
#define next(x) next_permutation(all(x))
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define cnt(x,a) count(all(x),a)
#define n(x) int((x).size())
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define ub upper_bound
#define lb lower_bound
#define Unique(x) (x).erase(unique(all(x)),(x).end())
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define error cout<<-1<<nl
#define space ' '
#define nl '\n'
#define pi acos(-1)
#define eps 1e-9
#define sqr(x) (1LL*(x)*(x))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (1LL*(a/gcd(a,b))*b)
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define SUM(a) accumulate(all(a),0LL)
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())
#define dbg(x) cerr<<#x<<" is "<<x<<'\n';
#define fix(x) cout<<fixed<<setprecision(x)
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;
#define time() cerr<<"Time elapsed : "<<clock()*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n'
///.........Bit_Manipulation...........///
#define MSB(mask) 63-__builtin_clzll(mask) /// 0 -> -1
#define LSB(mask) __builtin_ctzll(mask) /// 0 -> 64
#define SETBIT(mask) __builtin_popcountll(mask)
#define CHECKBIT(mask,bit) (mask&(1LL<<bit))
#define ONBIT(mask,bit) (mask|(1LL<<bit))
#define OFFBIT(mask,bit) (mask&~(1LL<<bit))
#define CHANGEBIT(mask,bit) (mask^(1LL<<bit))
///................Graph's Move.................
///const int dx[] = {+1,-1,+0,+0}; ///Rock's Move
///const int dy[] = {+0,+0,+1,-1}; ///Rock's Move
///const int dx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's Move
///const int dy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int dx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's Move
///const int dy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's Move
///*.....................-_-........................*///
vector<int>pf(N);
void smallestpf()
{
for(int i=2; i<N; i+=2)
pf[i]=2,pf[i-1]=i-1;
for(int i=3; i*i<N; i+=2)
if(pf[i]==i)
for(int j=i*i; j<N; j+=2*i)
if(pf[j]==j)
pf[j]=i;
}
vii factorization(int x)
{
vii v;
for(int i=pf[x]; i>1; i=pf[x])
{
while(x%i==0)
x/=i;
v.pb(i);
}
return v;
}
vvii d(N);
void pre()
{
for(int i=1; i<N; i++)
for(int j=i; j<N; j+=i)
d[j].pb(i);
}
orderset<int>st[N];
void Insert(int x,int in)
{
for(auto i:d[x])
st[i].insert(in);
}
void Erase(int x,int in)
{
for(auto i:d[x])
st[i].erase(in);
}
int main() /** "So which of the favors of your Lord(Allah) would you deny?" **/
{
///input;
///output;
fast();
int tc=1,cs=0;
pre();
smallestpf();
///cin>>tc;
while(tc--)
{
int n,q;
cin>>n;
vii v(n);
cinv(v);
for(int i=0; i<n; i++)
Insert(v[i],i+1);
cin>>q;
while(q--)
{
int type;
cin>>type;
if(type==1)
{
int l,r;
cin>>l>>r;
l--;
Erase(v[l],l+1);
v[l]=r;
Insert(v[l],l+1);
}
else
{
int l,r,k;
cin>>l>>r>>k;
vii ans=factorization(k);
int tot=r-l+1;
for(int i=1;i<(1<<n(ans));i++)
{
int c=0,d=1;
for(int j=0;j<n(ans);j++)
if(CHECKBIT(i,j))
c^=1,d*=ans[j];
int oc=st[d].order_of_key(r+1)-st[d].order_of_key(l);
if(c)
tot-=oc;
else
tot+=oc;
}
cout<<tot<<nl;
}
}
}
}Chef and Gcd Queries CodeChef Solution in C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h> // for srand/rand
#include <float.h> // <!> for pow, compile with your gcm.sh with option -lm !!!
#include <math.h> // <!> for pow, compile with your gcm.sh with option -lm !!!
#define uint64_t unsigned long long // avoid stdint.h
#define int64_t signed long long // avoid stdint.h
#define uint unsigned int
// my ordinarily lazy semantic ^^
#define uc unsigned char
#define us unsigned short
#define pf printf
#define print printf("\n");
#define LOOP1(x) for(fn1=0;fn1<(x);fn1++)
#define LOOP2(x) for(fn2=0;fn2<(x);fn2++)
#define LOOP3(x) for(fn3=0;fn3<(x);fn3++)
#define LOOP4(x) for(fn4=0;fn4<(x);fn4++)
#define LOOP5(x) for(fn5=0;fn5<(x);fn5++)
#define LOOP6(x) for(fn6=0;fn6<(x);fn6++)
#define LOOP(x,y) for(x=0;x<y;x++)
#define ifz(x) if(!(x))
#define ifnz(x) if(x)
uint mymin(uint a, uint b) { return a<=b?a:b; }
uint mymax(uint a, uint b) { return a>=b?a:b; }
int mysmax(int a, int b) { return a>=b?a:b; }
#define macro_dbl_malloc(array, dim1, dim2, arraytype, idx) \
array = (arraytype **) malloc((dim1) * sizeof(arraytype *)); \
LOOP(idx, dim1) { array[idx] = (arraytype *) malloc((dim2) * sizeof(arraytype)); }
#define getbitN32 __builtin_popcount
#define getbitN64 __builtin_popcountll
#define getbitN __builtin_popcountll
// 1-bit mask from bit bitpos to bit 63 INcluded
#define zmask64_Get(bitpos) (-1ULL << (bitpos))
// 1-bit mask from bit 0 to bit bitpos INcluded
// HS pour bitpos = 63 : plafonne aux 63 1ers bits
// #define mask64_Get(bitpos) ((1ULL << (mymin(63, (bitpos) + 1))) - 1ULL)
// OK avec bitpos 0, 63... nimp
#define mask64_Get(bitpos) (((1ULL << (bitpos)) - 1) | (1ULL << (bitpos)))
//#######################################
// OUT: get an unsigned integer from stdin
uint Uint32_Get() {
uint num= 0;
char c= getchar_unlocked();
while(!(c>='0' & c<='9'))
c= getchar_unlocked();
while(c>='0' && c<='9') {
num= (num<<1) + (num<<3) + c - '0';
c= getchar_unlocked();
}
return num;
}
//#######################################
// OUT: get an unsigned 64-bit integer from stdin
uint64_t Uint64_Get() {
uint64_t num= 0;
char c= getchar_unlocked();
while(!(c>='0' & c<='9'))
c= getchar_unlocked();
while(c>='0' && c<='9') {
num= (num<<1) + (num<<3) + c - '0';
c= getchar_unlocked();
}
return num;
}
//#######################################
// ajout ce 10/08/2017 pour HILLJUMP10.c
int cmp_dec_ull( const void* a, const void* b ) {
uint64_t* arg1 = (uint64_t*) a;
uint64_t* arg2 = (uint64_t*) b;
if( *arg1 < *arg2 ) return 1;
else if( *arg1 == *arg2 ) return 0;
else return -1;
}
//#######################################
int cmp_inc_ull( const void* a, const void* b ) {
uint64_t* arg1 = (uint64_t*) a;
uint64_t* arg2 = (uint64_t*) b;
if( *arg1 > *arg2 ) return 1;
else if( *arg1 == *arg2 ) return 0;
else return -1;
}
//#######################################
void SortedUint64ArrayNoDup_Get(uint64_t *tarray, uint *len) {
uint fn1, fn2 = 1;
for(fn1 = 1; fn1 < *len; fn1++) {
if(tarray[fn1] != tarray[fn2 - 1])
tarray[fn2++] = tarray[fn1];
}
*len = fn2;
}
#define PRIME_N 676
const uint tprimes[PRIME_N] = { // up to sqrt(30,000,000)
317, 331,
337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171,
1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483,
1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787,
1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113,
2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767,
2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121,
3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313,
3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469,
3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631,
3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803,
3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153,
4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517,
4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691,
4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903,
4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051,
// 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237,
// 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437,
};
// travaux OK en POLY3.c
// AIM: tell if dividable by one of first 64 primes (except 2)
// add the init call inside main(): PGCD_Accel_Init(t4PGCD);
const uint tsmallprimes[64] = {
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313
};
uint64_t *t4PGCD, *t4reliK;
//#######################################
void PGCD_Accel100K_Init(uint64_t *tarray) {
uint fn1, fn2, fn3, fn4, fn5;
for(fn1 = 3; fn1 <= 100000; fn1++) {
fn3 = fn1;
fn2 = __builtin_ctz(fn3);
fn3 >>= fn2;
ifnz(fn2) {
tarray[fn1] = tarray[fn3];
t4reliK[fn1] = t4reliK[fn3];
}
else {
LOOP4(64) {
if((fn3 % tsmallprimes[fn4]) == 0) {
tarray[fn1] |= (1ULL << fn4);
fn3 /= tsmallprimes[fn4];
break;
}
}
tarray[fn1] |= tarray[fn3];
if((tarray[fn1] == 0) && (fn1 & 1)) {
for(fn4 = fn1; fn4 <= 100000; fn4 += fn1)
t4reliK[fn4] = fn1; // premier > 313
}
}
}
}
// source : /home/ylav/dev/C/2017/poly/polygone13b.c avec les cmtR, et POINPOLY.c
// IN-OUT: *r, *c
// CMT: dividing *r and *c as much as we can ; if output r == input r then both are 'primes between themselves' -- premiers entre eux
void Pgcd(unsigned int *r, unsigned int *c) {
unsigned int fn1, mini, maxi, tmp, reste;
if(*r == *c) {
*r = 1; *c = 1;
}
else {
fn1 =__builtin_ctz(*r | *c);
*r >>= fn1;
*c >>= fn1;
maxi = *r >> __builtin_ctz(*r); // 2 n'est plus un diviseur commun et l'un des deux termes peut etre pair
mini = *c >> __builtin_ctz(*c); // 2 n'est plus un diviseur commun et l'un des deux termes peut etre pair
if(*r < *c) {
tmp = mini; mini = maxi; maxi = tmp; // swap
}
if(mini > 2) {
do {
reste = maxi % mini;
maxi = mini;
mini = reste;
} while(reste != 0);
if(maxi != 1) { // evite deux divisions souvent inutiles grace a ce IF
*r /= maxi;
*c /= maxi;
}
}
// printf("*r = %u, *c = %u\n", *r, *c);
}
}
#define LIST_N 1
#define GCD_AND 127 // 1023 0.68 s // 511 0.67 s // 255 0.7s // 127 tres bien ! 0.57 s // 31 // 63 // 15 // 7
typedef struct S_lsu {
uint prev;
uint next;
uint i;
uint q; // align16, unused
}Slsu;
Slsu *tlist[LIST_N];
#define LSU_HDR_SZ 4
#define LSU_HDR_HEAD lsu[0].next
#define LSU_HDR_QUEUE lsu[0].q
#define LSU_HDR_OCCN lsu[0].i
#define LSU_HDR_FIRST_AVAIL lsu[1].q
#define macro_lsu_queue(lsu) lsu[0].q
void List_Init(Slsu *lsu) {
uint fn1;
lsu[0].prev = 0;
lsu[0].next = LSU_HDR_SZ;
LSU_HDR_OCCN = 0; // nb d'elements actifs dans la liste
LSU_HDR_QUEUE = 0; // indice de queue
LSU_HDR_FIRST_AVAIL = LSU_HDR_SZ; // indice de 1re place dispo
}
// normal add: consecutive or not
uint Lsu_Add(Slsu *lsu, const uint i) {
uint n = LSU_HDR_FIRST_AVAIL;
lsu[n].i = i;
lsu[n].next = 0;
lsu[n].prev = LSU_HDR_QUEUE;
lsu[LSU_HDR_QUEUE].next = n;
LSU_HDR_QUEUE = n;
LSU_HDR_FIRST_AVAIL++;
LSU_HDR_OCCN++;
return n;
}
void Lsu_Remove2(Slsu lsu[], const uint idx) {
uint next = lsu[idx].next;
uint prev = lsu[idx].prev;
ifz(next)
LSU_HDR_QUEUE = prev;
else
lsu[next].prev = prev;
lsu[prev].next = next;
LSU_HDR_OCCN--;
}
void Lsu_Print(Slsu lsu[]) {
uint fn1, n = LSU_HDR_OCCN, next = LSU_HDR_HEAD;
LOOP1(n) {
pf("(cur=%u) .i = %u, prev = %u, next = %u\n", next, lsu[next].i, lsu[next].prev, lsu[next].next);
next = lsu[next].next;
}
}
// AIM: tu SAIS que 'searched' n'existe pas, tu t'arretes juste avant (pour future insertion en fait)
// IN: 'idx' is the head of chunk 'chunkI' and is BELOW 'searched'
// OUT: the list place just before the value 'searched'
uint LsuPrev_Search(Slsu lsu[], uint idx, const uint chunkI, const uint searched) {
uint cur = lsu[idx].next, old = idx; // old = idx tres important si cur == 0
while(cur != 0) {
old = cur;
if(lsu[cur].i > searched) {
return lsu[cur].prev;
}
cur = lsu[cur].next;
}
return old;
}
// CMT: LSU_HDR_QUEUE est gere, c + propre ; et cas special si 1re (re)insertion
uint Lsu_Insert(Slsu *lsu, const uint prev, const uint i) {
uint n = LSU_HDR_FIRST_AVAIL;
uint next = lsu[prev].next;
ifnz(LSU_HDR_OCCN) {
lsu[n].i = i;
lsu[n].prev = prev;
lsu[n].next = next;
lsu[prev].next = n;
ifnz(next)
lsu[next].prev = n;
else
LSU_HDR_QUEUE = n;
}
else { // ce cas, pour eviter que n.prev pointe sur... n
lsu[0].next = n;
LSU_HDR_QUEUE = n;
lsu[n].i = i;
lsu[n].prev = 0;
lsu[n].next = 0;
}
LSU_HDR_FIRST_AVAIL++;
LSU_HDR_OCCN++;
return n;
}
typedef struct S_lsudata {
uint64_t gcdmask;
uint reliK;
uint v; // tA = input data
}Slsudata;
Slsudata *tdata;
void Lsudata_Print(Slsu lsu[], Slsudata lsudata[]) {
uint fn1, n = LSU_HDR_OCCN, next = LSU_HDR_HEAD;
LOOP1(n) {
pf("(cur=%u) .i = %u, pointed data = %u, prev = %u, next = %u\n", next, lsu[next].i, lsudata[lsu[next].i].v, lsu[next].prev, lsu[next].next);
next = lsu[next].next;
}
}
// IN: tpos, alloc 32
// OUT: 1-bit positions into tpos, and bitN
void UintBitPos_Get(uint i, uint *tpos, uint *bitN) {
*bitN = 0;
while(i) {
tpos[*bitN] = __builtin_ctz(i);
i ^= (1U << tpos[*bitN]);
(*bitN)++;
}
}
// IN: tpos, alloc 64
// OUT: 1-bit positions into tpos, and bitN
void Uint64BitPos_Get(uint64_t i, uint *tpos, uint *bitN) {
*bitN = 0;
while(i) {
tpos[*bitN] = __builtin_ctzll(i);
i ^= (1ULL << tpos[*bitN]);
(*bitN)++;
}
}
uint64_t *tA;
typedef struct S_Q {
uint ty;
uint xL;
uint yR;
uint G;
}SQ;
SQ *tQ;
//#######################################
int main(void) {
uint64_t gcdmask, reliK, bit, l1, l2, Q1N, Q2N, *tsort, **ttrunk64, lxor, gcdnew, startmask, endmask;
uint N, Q, L, R, G, G2, A, ans, start, end, len, lsI, chunkI, i, j, v, w, head, prev, cur, next, lsN, sortN, u64N, u64mod, u64Ntot, tpos[32], bitN, primeI, *tprimeI, fn1, fn2, fn3, fn4;
t4PGCD = (uint64_t *)calloc(1, 100008 * sizeof(uint64_t));
t4reliK= (uint64_t *)calloc(1, 100008 * sizeof(uint64_t));
PGCD_Accel100K_Init(t4PGCD);
tprimeI = (uint *)calloc(1, 100008 * sizeof(uint));
primeI = 65; // deja 65 primes < 317
for(fn1 = 317; fn1 <= 99999; fn1 += 2) {
if(t4reliK[fn1])
tprimeI[fn1] = primeI++;
}
// 35385 -- pf("primeI %u\n", primeI);
LOOP1(LIST_N)
tlist[fn1] = (Slsu *)malloc(100008 * sizeof(Slsu));
tdata = (Slsudata *)malloc(50008 * sizeof(Slsudata));
macro_dbl_malloc(ttrunk64, primeI, ((50000 + 63) / 64), uint64_t, fn1);
tA = (uint64_t *)calloc(50004, sizeof(uint64_t));
tsort = (uint64_t *)malloc(50004 * sizeof(uint64_t));
tQ = (SQ *)calloc(50001, sizeof(SQ));
N = Uint32_Get();
LOOP1(N)
tA[fn1] = Uint64_Get();
Q = Uint32_Get();
LOOP1(Q) {
tQ[fn1].ty = Uint32_Get() - 1;
ifz(tQ[fn1].ty) {
tQ[fn1].xL = Uint32_Get() - 1;
tQ[fn1].yR = Uint32_Get();
}
else {
tQ[fn1].xL = Uint32_Get() - 1;
tQ[fn1].yR = Uint32_Get() - 1;
tQ[fn1].G = Uint32_Get();
}
}
if(N <= 0) { // 1000) {
LOOP1(Q) {
ifz(tQ[fn1].ty) {
tA[tQ[fn1].xL] = tQ[fn1].yR;
}
else {
L = tQ[fn1].xL;
R = tQ[fn1].yR;
G = tQ[fn1].G;
ans = 0;
for(fn2 = L; fn2 <= R; fn2++) {
A = tA[fn2];
G2 = G;
Pgcd(&A, &G2);
ans += (A == tA[fn2]);
}
pf("%u\n", ans);
}
}
}
else {
LOOP1(N) {
fn2 = tA[fn1];
tdata[fn1].v = fn2;
tdata[fn1].gcdmask = t4PGCD[fn2];
tdata[fn1].reliK = t4reliK[fn2];
}
u64N = N / 64;
u64mod = N & 63;
u64Ntot = u64N + (u64mod != 0);
// degrader G
sortN = 0; Q1N = 0;
LOOP1(Q) {
if(tQ[fn1].ty) {
L = tQ[fn1].xL;
R = tQ[fn1].yR;
G = tQ[fn1].G;
gcdmask = t4PGCD[G];
reliK = t4reliK[G];
if(gcdmask | reliK | ((G ^ 1) & 1)) {
fn2 = ((G ^ 1) & 1) + 1;
l1 = gcdmask;
while(l1) {
bit = __builtin_ctzll(l1);
fn2 *= tsmallprimes[bit];
l1 ^= (1ULL << bit);
}
tQ[fn1].G = fn2;
if(reliK)
tQ[fn1].G *= reliK;
}
else { // G reste G
}
tsort[sortN++] = tQ[fn1].G;
}
}
Q1N = sortN;
Q2N = Q - Q1N;
qsort(tsort, sortN, 8, cmp_inc_ull);
SortedUint64ArrayNoDup_Get(tsort, &sortN);
LOOP1(sortN)
if(tsort[fn1] > 313) break;
for(; fn1 < sortN; fn1++) {
l1 = tsort[fn1];
if(tprimeI[l1] >= 65) {
LOOP2(u64Ntot)
ttrunk64[tprimeI[l1]][fn2] = 0;
}
}
LOOP1(N) {
reliK = tdata[fn1].reliK;
ifnz(reliK) {
ttrunk64[tprimeI[reliK]][fn1 >> 6] |= (1ULL << (fn1 & 63));
}
}
#ifdef DEBUG
pf("Q1N %lu => sortN %lu, soit %5.1f %%\n", Q1N, sortN, (float)(sortN * 100) / (float)Q1N);
LOOP1(sortN) if(tsort[fn1] > GCD_AND) break;
pf("G avec diviseurs <= %u : %u\n", GCD_AND, fn1);
fn2 = 0; fn3 = 0;
LOOP1(Q) {
if(tQ[fn1].ty) {
fn3++;
if(tQ[fn1].G <= GCD_AND)
fn2++;
}
}
pf("%u occ en fait. Sur %u ; soit %5.1f %%\n", fn2, fn3, (float)(fn2 * 100) / (float)fn3);
exit(0);
#endif
l2 = 0;
LOOP1(65)
LOOP2(u64Ntot)
ttrunk64[fn1][fn2] = 0;
LOOP1(u64N) {
LOOP2(64) {
l1 = tdata[fn1 * 64 + fn2].gcdmask;
while(l1) {
bit = __builtin_ctzll(l1);
l1 ^= (1ULL << bit);
ttrunk64[bit][fn1] |= (1ULL << fn2);
}
// 2 est a part
fn3 = tdata[fn1 * 64 + fn2].v;
ifz(fn3 & 1)
ttrunk64[64][fn1] |= (1ULL << fn2);
}
}
// idem, reliquat
LOOP2(u64mod) {
l1 = tdata[fn1 * 64 + fn2].gcdmask;
while(l1) {
bit = __builtin_ctzll(l1);
l1 ^= (1ULL << bit);
ttrunk64[bit][fn1] |= (1ULL << fn2);
}
// 2 est a part
fn3 = tdata[fn1 * 64 + fn2].v;
ifz(fn3 & 1)
ttrunk64[64][fn1] |= (1ULL << fn2);
}
// OK, 5 % du tps jusqu'alors -- pf("l2 %lu\n", l2);
LOOP1(Q) {
ifz(tQ[fn1].ty) {
L = tQ[fn1].xL;
v = tQ[fn1].yR;
gcdnew = t4PGCD[v];
lxor = tdata[L].gcdmask ^ gcdnew;
l1 = lxor & tdata[L].gcdmask; // bits perdus
while(l1) {
bit = __builtin_ctzll(l1);
l1 ^= (1ULL << bit);
ttrunk64[bit][L >> 6] &= ~(1ULL << (L & 63));
}
l2 = lxor & gcdnew; // bits gagnes
while(l2) {
bit = __builtin_ctzll(l2);
l2 ^= (1ULL << bit);
ttrunk64[bit][L >> 6] |= (1ULL << (L & 63));
}
// division par 2 : changee ?
if(tdata[L].v & 1) {
ifz(v & 1)
ttrunk64[64][L >> 6] |= (1ULL << (L & 63));
}
else {
if(v & 1)
ttrunk64[64][L >> 6] ^= (1ULL << (L & 63));
}
// reliK AOT
ifnz(tdata[L].reliK) {
fn2 = tprimeI[tdata[L].reliK];
ttrunk64[fn2][L >> 6] ^= (1ULL << (L & 63));
}
// reliK a ajouter
ifnz(t4reliK[v]) {
fn2 = tprimeI[t4reliK[v]];
ttrunk64[fn2][L >> 6] |= (1ULL << (L & 63));
}
// update data
tdata[L].v = v;
tdata[L].gcdmask = t4PGCD[v];
tdata[L].reliK = t4reliK[v];
}
else {
ans = 0;
L = tQ[fn1].xL;
R = tQ[fn1].yR;
G = tQ[fn1].G;
gcdmask = t4PGCD[G];
reliK = t4reliK[G];
l1 = gcdmask;
Uint64BitPos_Get(l1, tpos, &bitN);
start = (L + 64) >> 6;
end = R >> 6;
ifz(reliK) { // ca gagne plusieurs tests :)
if(G & 1) {
for(fn2 = start; fn2 < end; fn2++) {
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 = ~l2;
ans += getbitN64(l2);
}
if((L >> 6) != (R >> 6)) {
startmask = zmask64_Get(L & 63);
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 = ~l2 & startmask;
ans += getbitN64(l2);
endmask = mask64_Get(R & 63);
fn2 = R >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 = ~l2 & endmask;
ans += getbitN64(l2);
}
else {
startmask = zmask64_Get(L & 63);
endmask = mask64_Get(R & 63);
startmask &= endmask;
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 = ~l2 & startmask;
ans += getbitN64(l2);
}
}
else { // G divisible par 2
for(fn2 = start; fn2 < end; fn2++) {
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 = ~l2;
ans += getbitN64(l2);
}
if((L >> 6) != (R >> 6)) {
startmask = zmask64_Get(L & 63);
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 = ~l2 & startmask;
ans += getbitN64(l2);
endmask = mask64_Get(R & 63);
fn2 = R >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 = ~l2 & endmask;
ans += getbitN64(l2);
}
else {
startmask = zmask64_Get(L & 63);
endmask = mask64_Get(R & 63);
startmask &= endmask;
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 = ~l2 & startmask;
ans += getbitN64(l2);
}
}
}
else {
primeI = tprimeI[reliK];
if(G & 1) {
for(fn2 = start; fn2 < end; fn2++) {
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2;
ans += getbitN64(l2);
}
if((L >> 6) != (R >> 6)) {
startmask = zmask64_Get(L & 63);
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & startmask;
ans += getbitN64(l2);
endmask = mask64_Get(R & 63);
fn2 = R >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & endmask;
ans += getbitN64(l2);
}
else {
startmask = zmask64_Get(L & 63);
endmask = mask64_Get(R & 63);
startmask &= endmask;
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & startmask;
ans += getbitN64(l2);
}
}
else { // G divisible par 2
for(fn2 = start; fn2 < end; fn2++) {
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2;
ans += getbitN64(l2);
}
if((L >> 6) != (R >> 6)) {
startmask = zmask64_Get(L & 63);
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & startmask;
ans += getbitN64(l2);
endmask = mask64_Get(R & 63);
fn2 = R >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & endmask;
ans += getbitN64(l2);
}
else {
startmask = zmask64_Get(L & 63);
endmask = mask64_Get(R & 63);
startmask &= endmask;
fn2 = L >> 6;
fn4 = fn2 * 64;
l2 = 0;
LOOP3(bitN) {
bit = tpos[fn3];
l2 |= ttrunk64[bit][fn2];
}
l2 |= ttrunk64[64][fn2]; // div par 2
l2 |= ttrunk64[primeI][fn2];
l2 = ~l2 & startmask;
ans += getbitN64(l2);
}
}
}
pf("%u\n", ans);
continue;
}
}
}
exit(0);
}Chef and Gcd Queries CodeChef Solution in JAVA
import java.util.BitSet;
import java.util.Scanner;
class Megatron
{
//Prime Factorization Credits:geeksforgeeks
static final int MAXN = 100001;
static int spf[] = new int[MAXN];
static void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
if (spf[i] == i)
{
for (int j=i*i; j<MAXN; j+=i)
if (spf[j]==j)
spf[j]=i;
}
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int gg,hh,i,j,x,xx,yy,ll,rr,g;
gg=sc.nextInt();
int r[]=new int[gg+1];
BitSet bs[]=new BitSet[100001];
for(i=1;i<=100000;i++)
bs[i]=new BitSet(gg+1);
sieve();
for(i=1;i<=gg;i++)
{
r[i]=sc.nextInt();
x=r[i];
while(x!=1)
{
bs[spf[x]].set(i);
x=x/spf[x];
}
}
hh=sc.nextInt();
while(hh-->0)
{
if(sc.nextInt()==1)
{
xx=sc.nextInt();
yy=sc.nextInt();
x=r[xx];
while(x!=1)
{
bs[spf[x]].clear(xx);
x=x/spf[x];
}
r[xx]=yy;
x=r[xx];
while(x!=1)
{
bs[spf[x]].set(xx);
x=x/spf[x];
}
}
else
{
ll=sc.nextInt();
rr=sc.nextInt();
g=sc.nextInt();
BitSet bn=new BitSet(gg+1);
x=g;
while(x!=1)
{
bn.or(bs[spf[x]]);
x=x/spf[x];
}
bn=bn.get(ll,rr+1);
System.out.println(""+(rr-ll+1-bn.cardinality()));
}
}
}
}Chef and Gcd Queries CodeChef Solution in PYPY 3
#dung inclusion-exclusion method, gia su cac prime divisor of x la [2,3,5]
#=> tim trong doan l..r co bao nhieu so khong la coprime cua x => tim so so chia het cho 1, 2, 5, 6, 15, 30
#neu subset tao tu so le thi cong vao khong thi tru di
#=> voi moi square free integer i tu 1..100000, store cac index cua cac so trong array ma co divisor la i
#roi dung binary search + in-ex method
n = int(input())
s = list(map(int, input().split()))
q = int(input())
pd = [[] for _ in range(100001)]
for i in range(2, 100001):
if not pd[i]:
for j in range(i, 100001, i):
pd[j].append(i)
sfi = [[] for _ in range(100001)]
def enum(num):
for mask in range(1, 1 << len(pd[num])):
c = 1
on = 0
for i,j in enumerate(pd[num]):
if mask & 1 << i:
c *= j
on += 1
yield c, on
from bisect import bisect_left, bisect, insort
for i, num in enumerate(s):
for c, _ in enum(num):
sfi[c].append(i)
def update(pos, val):
pos -= 1
for c, _ in enum(s[pos]):
sfi[c].remove(pos)
for c,_ in enum(val):
insort(sfi[c], pos)
s[pos] = val
def query(l, r, val):
l -= 1
r -= 1
ans = r - l + 1
for c, on in enum(val):
left = bisect_left(sfi[c], l)
right = bisect(sfi[c], r)
if left == len(sfi[c]) or right == 0:
continue
diff = right - left
if on % 2 :
ans -= diff
else:
ans += diff
print (ans)
for _ in range(q):
_, *op = list(map(int, input().split()))
if len(op) == 3:
query(*op)
else:
update(*op)Chef and Gcd Queries CodeChef Solution in PYTH
#!/usr/bin/python
def shed(n, f):
while n % f == 0:
n = n // f
return n
def getFactors(n):
ret = []
if n % 2 == 0:
ret.append(2)
n = shed(n, 2)
f = 3
while f * f <= n:
if n % f == 0:
ret.append(f)
n = shed(n, f)
f += 2
if n > 1:
ret.append(n)
return ret
def inclusionExclusion(n):
parity = 0
while n > 0:
parity += 1
n &= n - 1
if parity % 2 == 0:
return 1
else:
return -1
def lowerBound(lst, val):
first, count = 0, len(lst)
while count > 0:
step = count // 2
mid = first + step
if lst[mid] < val:
first = mid + 1
count -= step + 1
else:
count = step
return first
def upperBound(lst, val):
first, count = 0, len(lst)
while count > 0:
step = count // 2
mid = first + step
if val >= lst[mid]:
first = mid + 1
count -= step + 1
else:
count = step
return first
N, arr = int(raw_input()), map(int, raw_input().split())
multipleList = [[] for _ in range(100 * 1000 + 5)]
addList = [[] for _ in range(100 * 1000 + 5)]
subList = [[] for _ in range(100 * 1000 + 5)]
for i in range(N):
factors = getFactors(arr[i])
mask, combLen = 1, 2 ** len(factors)
while mask < combLen:
m, temp, idx = 1, mask, 0
while temp != 0:
if temp % 2 == 1:
m *= factors[idx]
idx += 1
temp = temp // 2
multipleList[m].append(i)
mask += 1
for _ in range(int(raw_input())):
rl = raw_input().split()
if rl[0] == '1':
pos, val = int(rl[1]) - 1, int(rl[2])
oldval = arr[pos]
factors = getFactors(oldval)
mask, combLen = 1, 2 ** len(factors)
while mask < combLen:
m, temp, idx = 1, mask, 0
while temp != 0:
if temp % 2 == 1:
m *= factors[idx]
idx += 1
temp = temp // 2
lb = lowerBound(subList[m], pos)
subList[m].insert(lb, pos)
mask += 1
arr[pos] = val
factors = getFactors(val)
mask, combLen = 1, 2 ** len(factors)
while mask < combLen:
m, temp, idx = 1, mask, 0
while temp != 0:
if temp % 2 == 1:
m *= factors[idx]
idx += 1
temp = temp // 2
lb = lowerBound(addList[m], pos)
addList[m].insert(lb, pos)
mask += 1
else:
L, R, G = int(rl[1]) - 1, int(rl[2]) - 1, int(rl[3])
ans = R - L + 1 # Inclusion of indices with factor 1
factors = getFactors(G)
mask, combLen = 1, 2 ** len(factors)
while mask < combLen:
m, temp, idx = 1, mask, 0
while temp != 0:
if temp % 2 == 1:
m *= factors[idx]
idx += 1
temp = temp // 2
cf = upperBound(multipleList[m], R) - lowerBound(multipleList[m], L)
cf -= upperBound(subList[m], R) - lowerBound(subList[m], L)
cf += upperBound(addList[m], R) - lowerBound(addList[m], L)
ans += inclusionExclusion(mask) * cf
mask += 1
print ansChef and Gcd Queries CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;
using static util;
using P = pair<int, int>;
using Binary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.ParameterExpression,
System.Linq.Expressions.BinaryExpression>;
using Unary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.UnaryExpression>;
class Program
{
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
static Scan sc = new Scan();
const int M = 1000000007;
// const int M = 998244353;
const long LM = (long)1e18;
const double eps = 1e-11;
static readonly int[] dd = { 0, 1, 0, -1, 0 };
static BIT_int[] bit;
static int[] lef, rig;
static void Main(string[] args)
{
const int lim = 100010;
var aa = sc.IntArr;
int n = aa[0];
int[] a;
int q;
if (aa.Length == 1) {
a = sc.IntArr;
q = sc.Int;
}
else if (aa.Length == 2) {
a = new int[n];
a[0] = aa[1];
var aaa = sc.IntArr;
for (int i = 1; i < n; i++)
{
a[i] = aaa[i - 1];
}
q = aaa[n - 1];
}
else {
throw new Exception();
}
var query = new int[q][];
for (int i = 0; i < q; i++)
{
query[i] = sc.IntArr;
--query[i][1];
}
if (Console.ReadLine() != null) {
int c = 1;
while (Console.ReadLine() != null)
{
++c;
}
if (c != a[0] - q) throw new Exception();
}
bit = new BIT_int[lim];
lef = new int[lim];
rig = new int[lim];
var lis = new List<int>[lim];
for (int i = 1; i < lim; i++)
{
lis[i] = new List<int>();
lef[i] = n;
rig[i] = 0;
int b = i;
for (int j = 2; j * j <= b; j++)
{
if (b % j == 0) {
lis[i].Add(j);
while (b % j == 0)
b /= j;
}
}
if (b > 1) lis[i].Add(b);
}
for (int i = 0; i < n; i++)
{
seg(i, lis[a[i]], 0, 1);
}
foreach (var item in query)
{
if (item[0] == 1) {
seg(item[1], lis[item[2]], 0, 1);
}
}
for (int i = 1; i < lim; i++)
{
if (lef[i] < rig[i])
bit[i] = new BIT_int(rig[i] - lef[i]);
}
for (int i = 0; i < n; i++)
{
inc(i, lis[a[i]], 0, 1);
}
foreach (var item in query)
{
if (item[0] == 1) {
int x = item[1], y = item[2];
if (a[x] == y) continue;
dec(x, lis[a[x]], 0, 1);
a[x] = y;
inc(x, lis[a[x]], 0, 1);
}
else {
int l = item[1], r = item[2], g = item[3];
Prt(count(l, r, lis[g], 0, 1));
}
}
sw.Flush();
}
static void seg(int x, List<int> lis, int k, int a) {
if (k == lis.Count) {
lef[a] = Math.Min(lef[a], x);
rig[a] = Math.Max(rig[a], x + 1);
return;
}
seg(x, lis, k + 1, a);
seg(x, lis, k + 1, a * lis[k]);
}
static void inc(int x, List<int> lis, int k, int a) {
if (k == lis.Count) {
bit[a].add(x - lef[a], 1);
return;
}
inc(x, lis, k + 1, a);
dec(x, lis, k + 1, a * lis[k]);
}
static void dec(int x, List<int> lis, int k, int a) {
if (k == lis.Count) {
bit[a].add(x - lef[a], -1);
return;
}
dec(x, lis, k + 1, a);
inc(x, lis, k + 1, a * lis[k]);
}
static int count(int l, int r, List<int> lis, int k, int a) {
if (k == lis.Count) {
int ll = Math.Max(l, lef[a]);
int rr = Math.Min(r, rig[a]);
if (ll < rr)
return bit[a].sum(ll - lef[a], rr - lef[a]);
else return 0;
}
return count(l, r, lis, k + 1, a) + count(l, r, lis, k + 1, a * lis[k]);
}
static void DBG(string a) => Console.WriteLine(a);
static void DBG<T>(IEnumerable<T> a) => DBG(string.Join(" ", a));
static void DBG(params object[] a) => DBG(string.Join(" ", a));
static void Prt(string a) => sw.WriteLine(a);
static void Prt<T>(IEnumerable<T> a) => Prt(string.Join(" ", a));
static void Prt(params object[] a) => Prt(string.Join(" ", a));
}
class pair<T, U> : IComparable<pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
public T v1;
public U v2;
public pair(T v1, U v2) {
this.v1 = v1;
this.v2 = v2;
}
public int CompareTo(pair<T, U> a) => v1.CompareTo(a.v1) != 0 ? v1.CompareTo(a.v1) : v2.CompareTo(a.v2);
public override string ToString() => v1 + " " + v2;
}
static class util
{
public static pair<T, T> make_pair<T>(this IList<T> l) where T : IComparable<T> => make_pair(l[0], l[1]);
public static pair<T, U> make_pair<T, U>(T v1, U v2) where T : IComparable<T> where U : IComparable<U> => new pair<T, U>(v1, v2);
public static T sqr<T>(T a) => Operator<T>.Multiply(a, a);
public static T Max<T>(params T[] a) => a.Max();
public static T Min<T>(params T[] a) => a.Min();
public static bool inside(int i, int j, int h, int w) => i >= 0 && i < h && j >= 0 && j < w;
public static void swap<T>(ref T a, ref T b) { var t = a; a = b; b = t; }
public static void swap<T>(this IList<T> a, int i, int j) { var t = a[i]; a[i] = a[j]; a[j] = t; }
public static T[] copy<T>(this IList<T> a) {
var ret = new T[a.Count];
for (int i = 0; i < a.Count; i++) ret[i] = a[i];
return ret;
}
}
static class Operator<T>
{
static readonly ParameterExpression x = Expression.Parameter(typeof(T), "x");
static readonly ParameterExpression y = Expression.Parameter(typeof(T), "y");
public static readonly Func<T, T, T> Add = Lambda(Expression.Add);
public static readonly Func<T, T, T> Subtract = Lambda(Expression.Subtract);
public static readonly Func<T, T, T> Multiply = Lambda(Expression.Multiply);
public static readonly Func<T, T, T> Divide = Lambda(Expression.Divide);
public static readonly Func<T, T> Plus = Lambda(Expression.UnaryPlus);
public static readonly Func<T, T> Negate = Lambda(Expression.Negate);
public static Func<T, T, T> Lambda(Binary op) => Expression.Lambda<Func<T, T, T>>(op(x, y), x, y).Compile();
public static Func<T, T> Lambda(Unary op) => Expression.Lambda<Func<T, T>>(op(x), x).Compile();
}
class Scan
{
public int Int => int.Parse(Str);
public long Long => long.Parse(Str);
public double Double => double.Parse(Str);
public string Str => Console.ReadLine().Trim();
public pair<T, U> Pair<T, U>() where T : IComparable<T> where U : IComparable<U>
{ T a; U b; Multi(out a, out b); return make_pair(a, b); }
public int[] IntArr => StrArr.Select(int.Parse).ToArray();
public long[] LongArr => StrArr.Select(long.Parse).ToArray();
public double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
public string[] StrArr => Str.Split(new []{' '}, System.StringSplitOptions.RemoveEmptyEntries);
bool eq<T, U>() => typeof(T).Equals(typeof(U));
T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
: eq<T, long>() ? ct<T, long>(long.Parse(s))
: eq<T, double>() ? ct<T, double>(double.Parse(s))
: eq<T, char>() ? ct<T, char>(s[0])
: ct<T, string>(s);
public void Multi<T>(out T a) => a = cv<T>(Str);
public void Multi<T, U>(out T a, out U b)
{ var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); }
public void Multi<T, U, V>(out T a, out U b, out V c)
{ var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); }
public void Multi<T, U, V, W>(out T a, out U b, out V c, out W d)
{ var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); }
public void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
{ var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); }
public void Multi<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f)
{ var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); f = cv<Y>(ar[5]); }
}
static class mymath
{
public static long Mod = 1000000007;
public static bool isprime(long a) {
if (a < 2) return false;
for (long i = 2; i * i <= a; i++) if (a % i == 0) return false;
return true;
}
public static bool[] sieve(int n) {
var p = new bool[n + 1];
for (int i = 2; i <= n; i++) p[i] = true;
for (int i = 2; i * i <= n; i++) if (p[i]) for (int j = i * i; j <= n; j += i) p[j] = false;
return p;
}
public static List<int> getprimes(int n) {
var prs = new List<int>();
var p = sieve(n);
for (int i = 2; i <= n; i++) if (p[i]) prs.Add(i);
return prs;
}
public static long[][] E(int n) {
var ret = new long[n][];
for (int i = 0; i < n; i++) { ret[i] = new long[n]; ret[i][i] = 1; }
return ret;
}
public static double[][] dE(int n) {
var ret = new double[n][];
for (int i = 0; i < n; i++) { ret[i] = new double[n]; ret[i][i] = 1; }
return ret;
}
public static long[][] pow(long[][] A, long n) {
if (n == 0) return E(A.Length);
var t = pow(A, n / 2);
if ((n & 1) == 0) return mul(t, t);
return mul(mul(t, t), A);
}
public static double[][] pow(double[][] A, long n) {
if (n == 0) return dE(A.Length);
var t = pow(A, n / 2);
if ((n & 1) == 0) return mul(t, t);
return mul(mul(t, t), A);
}
public static double dot(double[] x, double[] y) {
int n = x.Length;
double ret = 0;
for (int i = 0; i < n; i++) ret += x[i] * y[i];
return ret;
}
public static double _dot(double[] x, double[] y) {
int n = x.Length;
double ret = 0, r = 0;
for (int i = 0; i < n; i++) {
double s = ret + (x[i] * y[i] + r);
r = (x[i] * y[i] + r) - (s - ret);
ret = s;
}
return ret;
}
public static long dot(long[] x, long[] y) {
int n = x.Length;
long ret = 0;
for (int i = 0; i < n; i++) ret = (ret + x[i] * y[i]) % Mod;
return ret;
}
public static T[][] trans<T>(T[][] A) {
int n = A[0].Length, m = A.Length;
var ret = new T[n][];
for (int i = 0; i < n; i++) { ret[i] = new T[m]; for (int j = 0; j < m; j++) ret[i][j] = A[j][i]; }
return ret;
}
public static double[] mul(double a, double[] x) {
int n = x.Length;
var ret = new double[n];
for (int i = 0; i < n; i++) ret[i] = a * x[i];
return ret;
}
public static long[] mul(long a, long[] x) {
int n = x.Length;
var ret = new long[n];
for (int i = 0; i < n; i++) ret[i] = a * x[i] % Mod;
return ret;
}
public static double[] mul(double[][] A, double[] x) {
int n = A.Length;
var ret = new double[n];
for (int i = 0; i < n; i++) ret[i] = dot(x, A[i]);
return ret;
}
public static long[] mul(long[][] A, long[] x) {
int n = A.Length;
var ret = new long[n];
for (int i = 0; i < n; i++) ret[i] = dot(x, A[i]);
return ret;
}
public static double[][] mul(double a, double[][] A) {
int n = A.Length;
var ret = new double[n][];
for (int i = 0; i < n; i++) ret[i] = mul(a, A[i]);
return ret;
}
public static long[][] mul(long a, long[][] A) {
int n = A.Length;
var ret = new long[n][];
for (int i = 0; i < n; i++) ret[i] = mul(a, A[i]);
return ret;
}
public static double[][] mul(double[][] A, double[][] B) {
int n = A.Length;
var Bt = trans(B);
var ret = new double[n][];
for (int i = 0; i < n; i++) ret[i] = mul(Bt, A[i]);
return ret;
}
public static long[][] mul(long[][] A, long[][] B) {
int n = A.Length;
var Bt = trans(B);
var ret = new long[n][];
for (int i = 0; i < n; i++) ret[i] = mul(Bt, A[i]);
return ret;
}
public static long[] add(long[] x, long[] y) {
int n = x.Length;
var ret = new long[n];
for (int i = 0; i < n; i++) ret[i] = (x[i] + y[i]) % Mod;
return ret;
}
public static long[][] add(long[][] A, long[][] B) {
int n = A.Length;
var ret = new long[n][];
for (int i = 0; i < n; i++) ret[i] = add(A[i], B[i]);
return ret;
}
public static long pow(long a, long b) {
if (a >= Mod) return pow(a % Mod, b);
if (a == 0) return 0;
if (b == 0) return 1;
var t = pow(a, b / 2);
if ((b & 1) == 0) return t * t % Mod;
return t * t % Mod * a % Mod;
}
public static long inv(long a) => pow(a, Mod - 2);
public static long gcd(long a, long b) {
while (b > 0) { var t = a % b; a = b; b = t; } return a;
}
// a x + b y = gcd(a, b)
public static long extgcd(long a, long b, out long x, out long y) {
long g = a; x = 1; y = 0;
if (b > 0) { g = extgcd(b, a % b, out y, out x); y -= a / b * x; }
return g;
}
public static long lcm(long a, long b) => a / gcd(a, b) * b;
static long[] facts;
public static long[] setfacts(int n) {
facts = new long[n + 1];
facts[0] = 1;
for (int i = 0; i < n; i++) facts[i + 1] = facts[i] * (i + 1) % Mod;
return facts;
}
public static long comb(int n, int r) {
if (n < 0 || r < 0 || r > n) return 0;
if (n - r < r) r = n - r;
if (r == 0) return 1;
if (r == 1) return n;
if (facts != null && facts.Length > n) return facts[n] * inv(facts[r]) % Mod * inv(facts[n - r]) % Mod;
int[] numer = new int[r], denom = new int[r];
for (int k = 0; k < r; k++) { numer[k] = n - r + k + 1; denom[k] = k + 1; }
for (int p = 2; p <= r; p++) {
int piv = denom[p - 1];
if (piv > 1) {
int ofst = (n - r) % p;
for (int k = p - 1; k < r; k += p) { numer[k - ofst] /= piv; denom[k] /= piv; }
}
}
long ret = 1;
for (int k = 0; k < r; k++) if (numer[k] > 1) ret = ret * numer[k] % Mod;
return ret;
}
public static long[][] getcombs(int n) {
var ret = new long[n + 1][];
for (int i = 0; i <= n; i++) {
ret[i] = new long[i + 1];
ret[i][0] = ret[i][i] = 1;
for (int j = 1; j < i; j++) ret[i][j] = (ret[i - 1][j - 1] + ret[i - 1][j]) % Mod;
}
return ret;
}
// nC0, nC2, ..., nCn
public static long[] getcomb(int n) {
var ret = new long[n + 1];
ret[0] = 1;
for (int i = 0; i < n; i++) ret[i + 1] = ret[i] * (n - i) % Mod * inv(i + 1) % Mod;
return ret;
}
}
class BIT_int
{
int n;
int[] bit;
public BIT_int(int n) { this.n = n; bit = new int[n]; }
public void add(int j, int w) { for (int i = j; i < n; i |= i + 1) bit[i] += w; }
public int at(int j) => sum(j, j + 1);
// [0, j)
public int sum(int j) {
int ret = 0;
for (int i = j - 1; i >= 0; i = (i & i + 1) - 1) ret += bit[i];
return ret;
}
// [j, k)
public int sum(int j, int k) => sum(k) - sum(j);
}Chef and Gcd Queries CodeChef Solution Review:
In our experience, we suggest you solve this Chef and Gcd Queries CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and Gcd Queries CodeChef Solution.
Conclusion:
I hope this Chef and Gcd Queries CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
