Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Queries About Numbers CodeChef Solution
Problem -Queries About Numbers 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.
Queries About Numbers CodeChef Solution in C++14
#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds; //for policy based ds
using namespace std;
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
for (int &i : arr) \
cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
time_t Begin;
//////////////////Debug///////////////
#define debug(x) \
cout << #x << " "; \
_print(x); \
cout << endl;
void _print(ll t)
{
cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
for (ll i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
cout << "{";
_print(p.first);
cout << ",";
_print(p.second);
cout << "}";
}
template <class T>
void _print(vector<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(set<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
cout << "[ ";
for (auto i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
void init()
{
Begin = clock();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}
vector<int> computeLps(string s, int M)
{
int len = 0;
vector<int> lps(M + 20);
lps[0] = 0;
int i = 1;
while (i < M)
{
if (s[i] == s[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
// debug(len);
return lps;
}
int ceiling(int x, int y)
{
int res = x / y;
if (x % y)
{
if (x >= 0)
res++;
}
return res;
}
vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> prefix(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
}
}
return prefix;
}
int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
// cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}
int toInt(string &s)
{
int res = 0;
for (char c : s)
res = res * 10 + (c - '0');
return res;
}
bool isValid(int i, int j, int n, int m)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};
map<int, int> primeFactorization(int n)
{
map<int, int> mp;
for (int i = 2; i * i <= n; i++)
{
int exp = 0;
while (n % i == 0)
{
n /= i;
exp++;
}
if (exp)
mp[i] = exp;
}
if (n > 1)
{
mp[n] = 1;
}
return mp;
}
// const int MX = 100000;
int32_t main()
{
init();
//--------------------
int t = 1;
// cin >> t;
for (int tt = 1; tt <= t; tt++)
{
int n, q;
cin >> n >> q;
map<int, int> mp = primeFactorization(n);
int totalDivN = 1;
for (auto i : mp)
totalDivN *= i.second + 1;
// debug(mp);
while (q--)
{
int ty, k;
cin >> ty >> k;
int res = 1;
if (ty == 1)
{
int kk = k;
for (auto i : mp)
{
int cnt = 0;
while (kk % i.first == 0)
{
kk /= i.first;
cnt++;
}
res *= min(cnt, i.second) + 1;
}
if (n == 1)
res = 1;
}
else if (ty == 2)
{
int kk = k;
for (auto i : mp)
{
int cnt = 0;
while (kk % i.first == 0)
{
kk /= i.first;
cnt++;
}
res *= i.second - cnt + 1;
}
if (n % k != 0)
res = 0;
else if (n == k)
res = 1;
}
else
{
int kk = k;
for (auto i : mp)
{
int cnt = 0;
while (kk % i.first == 0)
{
kk /= i.first;
cnt++;
}
res *= i.second - cnt + 1;
}
if (n % k != 0)
res = 0;
else if (n == k)
res = 1;
res = totalDivN - res;
}
cout << res << "\n";
}
}
//---------------------------
timeTaken();
return 0;
}Queries About Numbers CodeChef Solution in PYTH 3
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
pfactors=[]
num=n
i=2
while((i*i)<=num):
if num%i==0:
num//=i
pfactors.append(i)
else:
i+=1
if num!=1:
pfactors.append(num)
nd=dict()
kd=dict()
#print(pfactors)
for i in pfactors:
nd[i]=0
kd[i]=0
for i in pfactors:
nd[i]+=1
#print(nd)
#print(kd)
for _ in range(q):
t,k=map(int,input().split())
if t==1:
if n==1:
print(1)
else:
if k==1:
print(1)
else:
for i in pfactors:
if k%i==0:
kd[i]+=1
k//=i
ans=1
for i in kd:
ans*=(kd[i]+1)
print(ans)
for i in kd:
kd[i]=0
elif t==2:
if n==1:
if k==1:
print(1)
else:
print(0)
elif k==1:
ans=1
for i in nd:
ans*=(nd[i]+1)
print(ans)
else:
if n%k!=0:
print(0)
else:
for i in nd:
kd[i]=nd[i]
for i in pfactors:
if k%i==0:
kd[i]-=1
k//=i
ans=1
for i in kd:
ans*=(kd[i]+1)
print(ans)
for i in kd:
kd[i]=0
else:
if n==1:
if k==1:
print(0)
else:
print(1)
elif k==1:
print(0)
else:
if n%k!=0:
ans=1
for i in nd:
ans*=(nd[i]+1)
print(ans)
else:
ans1=1
for i in nd:
ans1*=(nd[i]+1)
for i in nd:
kd[i]=nd[i]
for i in pfactors:
if k%i==0:
kd[i]-=1
k//=i
ans2=1
for i in kd:
ans2*=(kd[i]+1)
print(ans1-ans2)
for i in kd:
kd[i]=0Queries About Numbers CodeChef Solution in C
#include <stdio.h>
#define Int long long int
Int a[30][2]={0};
Int total=1;
int primefac(Int t){
int m=0;
for(Int i=2;i*i<=t;i++)
if(!(t%i)){
a[m++][0]=i;
while(!(t%i))a[m-1][1]++,t/=i;
}
if(t>1)
a[m++][0]=t,a[m-1][1]++;
for(int i=0;i<m;i++)
total*=(a[i][1]+1);
return m;
}
int min(int a,int b){
return a>b?b:a;
}
int main(){
Int n;
int q,t;
Int k;
scanf("%lld",&n);
int m=primefac(n);
scanf("%d",&q);
while(q--){
scanf("%d%lld",&t,&k);
Int res=1;
if(t==1){
for(int i=0;i<m;i++){
int u=0;
if(!(k%a[i][0])){
while(!(k%a[i][0])){
u++;
k/=a[i][0];
}}
res=res*1ll*(min(u,a[i][1])+1);
}
printf("%lld\n",res);}
else if(t==2){
if(n%k)
res=0;
else if(!(n%k)){
for(int i=0;i<m;i++){
int u=0;
if(!(k%a[i][0]) ){
while(!(k%a[i][0])){
u++;
k/=a[i][0];
}}
res=res*1ll*(a[i][1]-u+1);
}}
printf("%lld\n",res); }
else if(t==3){
if(n%k)
res=0;
else if(!(n%k)){
for(int i=0;i<m;i++){
int u=0;
if(!(k%a[i][0])){
while(!(k%a[i][0])){
u++;
k/=a[i][0];
}}
res=res*1ll*(a[i][1]-u+1);
}}
printf("%lld\n",total-res);
}
}
return 0;}Queries About Numbers CodeChef Solution in JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
static long total=1;
public static void main(String args[]) throws java.lang.Exception
{
FastScanner input = new FastScanner();
int t=1;
while(t-->0){
//write your code here
long N=input.nextLong();
long Q=input.nextLong();
HashMap<Long,Long> map=Factorize(N);
StringBuilder sb=new StringBuilder();
while(Q-->0){
int T=input.nextInt();
long K=input.nextLong();
if(T==1){
long ans=ResponseToQuery1(map,K);
sb.append(ans+"\n");
}else if(T==2){
long ans=ResponseToQuery2(map,K);
sb.append(ans+"\n");
}else if(T==3){
long ans=ResponseToQuery3(map,K);
sb.append(ans+"\n");
}
}
System.out.println(sb);
}
}
public static long ResponseToQuery3(HashMap<Long,Long>map,long K){
long val=ResponseToQuery2(map,K);
return (total-val);
}
public static long ResponseToQuery2(HashMap<Long,Long>map,long K){
long ans=1;
for(long key:map.keySet()){
long fac=key;
long val=map.get(key);
long cnt=0;
while(K%fac==0){
K/=fac;
cnt++;
}
if(cnt>val){
ans=0;break;
}
ans*=(val-cnt+1);
}
if(K>1)ans=0;
return ans;
}
public static long ResponseToQuery1(HashMap<Long,Long>map,long K){
// HashMap<Long,Long> qmap=new HashMap<>();
long ans=1;
for(long key:map.keySet()){
long fac=key;
long val=map.get(key);
long cnt=0;
while(K%fac==0){
K/=fac;
cnt++;
}
ans*=(Math.min(val,cnt)+1);
}
return ans;
}
public static HashMap<Long,Long> Factorize(long N){
HashMap<Long,Long> map=new HashMap<>();
for(long i=2;i*i<=N;i++){
if(N%i==0){
long f1=i;
long cnt=0;
while(N%f1==0){
N/=f1;cnt++;
}
if(cnt!=0)
map.put(f1,cnt);
total*=(cnt+1);
}
}
if(N>1){map.put(N,1L);total*=2;}
return map;
}
static class FastScanner
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next()
{
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine() throws IOException
{
return br.readLine();
}
}
}Queries About Numbers CodeChef Solution in PYPY 3
from math import ceil,gcd,factorial,sqrt,log,log2
import queue
# import re
# from functools import reduce
#product is used to generater truth tables or multiply list produc([0,1],repeat=n)
from itertools import permutations,combinations,accumulate,product
from collections import Counter,deque
from sys import stdin,stdout
from bisect import bisect,insort,bisect_left,insort_left
input=stdin.buffer.readline
# bisect=upper_bound,bisect_left=lower_bound
def sieve(n):
prime = [True]*(n+1)
p = 2
a=[]
for p in range(2,int(n**0.5)+1):
if (prime[p] == True):
a.append(p)
for l1 in range(p * p, n+1, p):
prime[l1] = False
return a
def simplesieve(n):
prime=[2]
mark=[False]*(n+1)
for p in range(3,n+1,2):
if(mark[p]==False):
prime.append(p)
if(p*p<=n):
for l1 in range(p*p,n +1,2*p):
mark[l1]=True
return prime
def segementedsieve(low,high):
primes=simplesieve(int(high**.5))
prime = [True] * (high-low + 1)
for i in primes:
lower = (low//i)*i
if lower<low:
lower+=i
for j in range(lower,high+1,i):
if(j!=i):
prime[j-low]=False
ans=[]
for i in range(low,high+1):
if prime[i-low]:
ans.append(i)
return ans
def isprime(n):
if(n==2):
return True
if(n%2==0 or n==1):
return False
for l1 in range(3,int(n**0.5)+1,2):
if(n%l1==0):
return False
return True
def binpow(a,b,m):
r2=1
a=a%m
while(b>0):
if(b&1):
r2=(r2*a)%m
a=(a*a)%m
b>>=1
return r2
def lcm(a,b):
return (a//gcd(a,b))*b
#gcd(a,b)=ax+by and
def gcdExtended(a,b):
if(b==0):
return a,1,0
g,x1,y1=gcdExtended(b,a%b)
x1,y1 = y1,x1-(a//b)*y1
return g,x1,y1
def binsearch(a,l,r,key):
while(r-l>1):
m=l+(r-l)//2
if(a[m]<=key):
l=m
else:
r=m
if(a[l]==key):
return l
if(a[r]==key):
return r
return -1
class Node():
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inorder(root):
res, stack = [], []
current = root
while True:
while current:
stack.append(current)
current = current.left
if len(stack) == 0:
return res
node = stack[-1]
stack.pop(len(stack)-1)
if node.data != None:
res.append(node.data)
current = node.right
return res
def dfs(graph,s,v,ans):
v[s]=1
ans.append(s)
for i in graph[s]:
if(v[i]==0):
dfs(graph,i,v,ans)
def bfs(graph,n,x,dest):
v=[0]*(1+n)
d=[0]*(1+n)
# d=[-1]*1000
d[x]=0
v[x]=1
q=queue.Queue()
q.put(x)
# p=[0]*(1+n)
# p[x]=-1
while(not q.empty()):
z=q.get()
for s in graph[z]:
if(v[s]==0):
v[s]=1
d[s]=d[z]+1
q.put(s)
# p[s]=z
# path=[]
# #l1=dest#given
# while(l1!=-1):
# path.append(l1)
# l1=p[l1]
# path.reverse()
#?print(d)
return d[dest]
# for _ in range(int(input())):
# n=int(input())
n,q=map(int,input().split())
# a=list(map(int,input().split()))
prime=Counter()
r=1
for i in range(2,int(n**0.5)+1):
if(n%i==0):
c=0
while(n%i==0):
n=n//i
c+=1
prime[i]=c
r=r*(c+1)
if(n>1):
prime[n]=1
r=r*2
t=len(prime)
for _ in range(q):
a,b=map(int,input().split())
c=Counter()
ans=1
if(a==1):
for i in prime:
if(b%i==0):
c=0
while(b%i==0):
b=b//i
c+=1
ans*=min(prime[i]+1,(c+1))
elif(a==2):
for i in prime:
if(b%i==0):
c=0
while(b%i==0):
b=b//i
c+=1
if(c>prime[i]):
ans=0
break
ans*=((prime[i]-c)+1)
else:
ans*=(prime[i]+1)
if(b>1):
ans=0
else:
for i in prime:
if(b%i==0):
c=0
while(b%i==0):
b=b//i
c+=1
if(c>prime[i]):
ans=0
break
ans*=((prime[i]-c)+1)
else:
ans*=(prime[i]+1)
if(b>1):
ans=0
ans=r-ans
print(ans)Queries About Numbers CodeChef Solution Review:
In our experience, we suggest you solve this Queries About Numbers 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 Queries About Numbers CodeChef Solution.
Conclusion:
I hope this Queries About Numbers 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!
