Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and cities CodeChef Solution
Problem -Chef and cities 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.
<<Previous CodeChef Problem Next Codechef Problem>>
Chef and cities CodeChef Solution in C++14
“#include<bits/stdc++.h>
using namespace std;
#define mx 200005
#define ll long long
#define mod 1000000007 //998244353
ll a[mx];
char ch[mx];
int n, m, ii, k;
ll ans[mx];
long double digit[mx];
vector<int>g[mx];
long double eps = 1e-6;
ll add(ll a, ll b)
{
a += b;
if (a >= mod)a -= mod;
return a;
}
ll sub(ll a, ll b)
{
a -= b;
if (a < 0)a += mod;
return a;
}
ll mul(ll a, ll b)
{
ll re = a;
re *= b;
if (re >= mod)re %= mod;
return re;
}
ll bigmod(ll b, ll e)
{
ll ans = 1;
while (e) {
if (e & 1)ans = mul(ans, b);
e >>= 1;
b = mul(b, b);
}
return ans;
}
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans[i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j += i) {
g[j].push_back(i);
ans[i] = mul(ans[i], a[j]);
digit[i] += log10(a[j] + eps);
}
}
int q;
scanf("%d", &q);
while (q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int id;
ll val;
scanf("%d%lld", &id, &val);
if (id == 1) {
a[id] = val;
}
else {
for (auto v : g[id]) {
ans[v] = mul(ans[v], bigmod(a[id], mod - 2));
digit[v] -= log10(a[id] + eps);
digit[v] += log10(val + eps);
ans[v] = mul(ans[v], val);
}
a[id] = val;
}
}
else {
int r;
scanf("%d", &r);
long double fractional = log10(a[1] + eps) + digit[r];
int re = pow(10.0, fractional - (ll)fractional);
// cout << ans[r] << " ";
ll answer = mul(ans[r], a[1]);
printf("%d %lld\n", re, answer);
}
}
return;
}
int main()
{
int t = 1;
// scanf("%d", &t);
for (int i = 1; i <= t; i++) {
// printf("Case %d: ", i);
solve();
}
return 0;
}Chef and cities CodeChef Solution in PYTH 3
“
import math
import sys
class Main:
def __init__( self ):
iterable = self.__input( )
iterable = self.__solution( iterable )
self.__output( iterable )
def __solution( self, iterable ):
iterable = map( int, iterable )
count = next( iterable )
data = [ next( iterable ) for _index in range( count ) ]
state = State( data )
queries = next( iterable )
for _index in range( queries ):
command = next( iterable )
if command == 1:
index = next( iterable ) - 1
value = next( iterable )
state.update( index, value )
else:
step = next( iterable )
digit, remainder = state.calculate( step )
yield digit
yield " "
yield str( remainder )
yield "\n"
def __input( self ):
yield from sys.stdin.buffer.raw.read( ).decode( ).split( )
def __output( self, iterable ):
sys.stdout.buffer.raw.write( "".join( iterable ).encode( ) )
class State:
def __init__( self, data ):
modulus = ( 10 ** 9 ) + 7
size = len( data )
self.__modulus = modulus
self.__remainders = data
self.__logarithms = [ math.fmod( math.log10( item ), 1 ) for item in data ]
self.__lookup = [ [ ] for _index in range( size ) ]
self.__remaindersN = [ 0 ]
self.__logarithmsN = [ 0 ]
for step in range( 1, size + 1 ):
product = 1
summa = 0
for index in range( step, size, step ):
product = product * data[ index ] % modulus
summa = math.fmod( summa + self.__logarithms[ index ], 1 )
self.__lookup[ index ].append( step )
self.__remaindersN.append( product )
self.__logarithmsN.append( summa )
def update( self, index, value ):
inverse = pow( self.__remainders[ index ], self.__modulus - 2, self.__modulus )
negative = 1 - self.__logarithms[ index ]
value0 = math.fmod( math.log10( value ), 1 )
self.__remainders[ index ] = value
self.__logarithms[ index ] = value0
for step in self.__lookup[ index ]:
self.__remaindersN[ step ] = ( self.__remaindersN[ step ] * inverse * value ) % self.__modulus
self.__logarithmsN[ step ] = math.fmod( self.__logarithmsN[ step ] + negative + value0, 1 )
def calculate( self, step ):
remainder = ( self.__remainders[ 0 ] * self.__remaindersN[ step ] ) % self.__modulus
logarithm = math.fmod( self.__logarithms[ 0 ] + self.__logarithmsN[ step ], 1 )
top = round( pow( 10, logarithm ), 9 )
return str( top )[ 0 ], remainder
if __name__ == "__main__":
Main( )Chef and cities CodeChef Solution in C
“
#include <stdio.h>
#include <math.h>
#define ll long long
#define gc getchar_unlocked
#define MOD 1000000007
int getn(){
int n = 0, c = gc(), f = 1;
while(c != '-' && (c < '0' || c > '9')) c = gc();
if(c == '-') f = -1, c = gc();
while(c >= '0' && c <= '9') n = (n<<3) + (n<<1) + c - '0', c = gc();
return n * f;
}
int mmul(int a, int b){ return (ll)a * b % MOD; }
int mpow(ll n, int e){
ll r = 1;
while(e){
if(e & 1) r = r * n % MOD;
n = n * n % MOD, e >>= 1;
}
return (int)r;
}
int a[100000], b[100000][256], bn[100000], p[100001];
double s[100001];
int main(){
int N,Q,O,P,F,R, i,j, u;
double t;
N = getn();
for(i = 0; i < N; ++i) a[i] = getn(), bn[i] = 0;
for(i = 1; i <= N; ++i) for(j = i, s[i] = 0, p[i] = 1; j < N; j += i)
p[i] = mmul(p[i], a[j]), s[i] += log10(a[j]), b[j][bn[j]++] = i;
Q = getn();
while(Q--){
O = getn();
if(O == 1){
P = getn()-1, F = getn();
if(!P){ a[0] = F; continue; }
for(i = 0; i < bn[P]; ++i)
p[b[P][i]] = mmul(mmul(p[b[P][i]], mpow(a[P], MOD-2)), F),
s[b[P][i]] += log10(F) - log10(a[P]);
a[P] = F;
}else{
R = getn();
t = s[R] + log10(a[0]);
u = (int)(pow(10, t-(int)t)+0.000000001);
while(u > 9) u /= 10;
printf("%d %d\n", u, mmul(p[R], a[0]));
}
}
return 0;
}Chef and cities CodeChef Solution in JAVA
“import java.io.*;
import java.util.*;
class frjump
{
static int mod=1000000007;
static int modinv(int a, int p)
{
if(p == 1)
{
return a%mod;
}
else if(p % 2==0)
{
int half = p/2;
long val = modinv(a, half);
val = (val * val)%mod;
return (int)val;
}
else
{
int half = p/2;
long val = modinv(a, half);
val = (((val* val)%mod)*a)%mod;
return (int)val;
}
}
public static void main(String args[])throws IOException
{
Reader sc=new Reader();
int n=sc.nextInt();
//int q=sc.nextInt();
List<Integer> list[]=new ArrayList[n];
//list[0]=new ArrayList<>();
for(int i=1;i<=n;i++)
{
list[i-1]=new ArrayList<>();
}
int arr[]=new int[n];
double log[]=new double[n];
int inv[]=new int[n];
long mult[]=new long[n];
double sum[]=new double[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
log[i]=Math.log10(arr[i]);
log[i]=log[i]-Math.floor(log[i]);
inv[i]=modinv(arr[i],mod-2);
mult[i]=1;
}
int first=arr[0];double lo=log[0];
for(int i=1;i<=n;i++)
{
for(int j=0;j<n;j=j+i)
{
list[j].add(i-1);
mult[i-1]=(mult[i-1]*arr[j])%mod;
sum[i-1]=(sum[i-1]+log[j]);
}
}
int q=sc.nextInt();
for(int z=0;z<q;z++)
{
int typ=sc.nextInt();
if(typ==1)
{
int ind=sc.nextInt();
int f=sc.nextInt();
double l=Math.log10(f);
l=l-Math.floor(l);
if(ind==1)
{
first=f;
lo=l;
}
else
{
for(int j=0;j<list[ind-1].size();j++)
{
int num=list[ind-1].get(j);
mult[num]=(mult[num]*f)%mod;
mult[num]=(mult[num]*inv[ind-1])%mod;
sum[num]=sum[num]+l-log[ind-1];
}
arr[ind-1]=f;
log[ind-1]=l;
inv[ind-1]=modinv(f,mod-2);
}
}
else
{
int ind=sc.nextInt();
double fv=sum[ind-1]+lo-log[0];
double f = fv -Math.floor(fv);
int fd = (int)Math.floor(Math.pow(10, f+0.000000000001));
if(fd == 10)
{
fd = 1;
}
long value = (mult[ind-1]*first)%mod;
value = (value * inv[0])%mod;
System.out.println(fd+" "+value);
}
//System.out.println(list[z]);
}
}
}
class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte [] buffer;
private int bufferPointer, bytesRead;
public Reader () {
din = new DataInputStream (System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader (String file_name) throws IOException {
din = new DataInputStream (new FileInputStream (file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine () throws IOException {
byte [] buf = new byte[1024];
int cnt = 0, c;
while ((c = read ()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String (buf, 0, cnt);
}
public int nextInt () throws IOException {
int ret = 0;
byte c = read ();
while (c <= ' ')
c = read ();
boolean neg = (c == '-');
if (neg)
c = read ();
do {
ret = ret * 10 + c - '0';
} while ((c = read ()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong () throws IOException {
long ret = 0;
byte c = read ();
while (c <= ' ')
c = read ();
boolean neg = (c == '-');
if (neg)
c = read ();
do {
ret = ret * 10 + c - '0';
} while ((c = read ()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble () throws IOException {
double ret = 0, div = 1;
byte c = read ();
while (c <= ' ')
c = read ();
boolean neg = (c == '-');
if (neg)
c = read ();
do {
ret = ret * 10 + c - '0';
} while ((c = read ()) >= '0' && c <= '9');
if (c == '.')
while ((c = read ()) >= '0' && c <= '9')
ret += (c - '0') / (div *= 10);
if (neg)
return -ret;
return ret;
}
private void fillBuffer () throws IOException {
bytesRead = din.read (buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read () throws IOException {
if (bufferPointer == bytesRead)
fillBuffer ();
return buffer[bufferPointer++];
}
public void close () throws IOException {
if (din == null)
return;
din.close ();
}
}Chef and cities CodeChef Solution in PYTH
“import math
n = int(raw_input())
friendliness = map(int, raw_input().split())
logSum = [0]
prodSum = [0]
d = [[] for i in range(n)]
for r in range(1, n+1):
l = 0
p = 1
for j in range(r,n, r):
l += math.log10(friendliness[j])
p = (p*friendliness[j])%(10**9 + 7)
d[j].append(r)
logSum.append(l)
prodSum.append(p)
# print logSum
# print prodSum
# print d
q = int(raw_input())
for t in range(q):
query = map(int, raw_input().split())
if query[0] == 2:
x = logSum[query[1]] + math.log10(friendliness[0]) - math.floor(logSum[query[1]] + math.log10(friendliness[0]))
s = str(math.pow(10,x))
# print 's =', s
answer = (prodSum[query[1]]*friendliness[0])%(10**9 + 7)
print s[0],answer
else:
r = query[1]
if r == 1:
friendliness[0] = query[2]
else:
temp = pow(friendliness[r-1], 10**9 + 7 - 2, 10**9 + 7)
# print 'inverse', temp
for j in d[r-1]:
prodSum[j] = (prodSum[j]*query[2]*temp)%(10**9+7)
logSum[j] += math.log10(query[2]) - math.log10(friendliness[r-1])
# print 'updated values'
# print prodSum
# print logSum
friendliness[r-1] = query[2]
# print friendlinessChef and cities CodeChef Solution in C#
“using System;
using System.Collections.Generic;
using System.Text;
namespace JUMP
{
class Querie
{
public int a, b, c;
public Querie(int a, int b)
{
this.a = a; this.b = b;
c = 0;
}
public Querie(int a, int b, int c)
{
this.a = a; this.b = b; this.c = c;
}
}
class Program
{
public static List<int>[] D = new List<int>[100001];
public static int[] A = new int[100001];
public const int mod = 1000000007;
public static int[] R = new int[100002];
public static double[] L = new double[100001];
public static double[] Log = new double[100001];
public static StringBuilder sb = new StringBuilder();
public static List<Querie> queries = new List<Querie>();
static void Main(string[] args)
{
int N, Q;
bool ok = true;
N = int.Parse(Console.ReadLine());
if (N > 10) ok = false;
string[] tokens = Console.ReadLine().Split(' ');
for (int i = 1; i <= N; i++)
{
A[i] = int.Parse(tokens[i-1]);
if (A[i] > 10) ok = false;
Log[i] = Math.Log10(A[i]);
}
// find the divisors
for (int i = 1; i <= N; i++)
{
D[i] = new List<int>();
}
int p;
for (int i = 1; i <= N; i++)
{
p = i;
while (p < N)
{
D[p + 1].Add(i);
p += i;
}
}
// preprocess
for (int i = 1; i <= N; i++)
{
R[i] = 1;
L[i] = 0.0;
p = 1 + i;
while(p<=N)
{
R[i] = mult(R[i], A[p]);
L[i] += Log[p];
p += i;
}
}
// read queries
Q = int.Parse(Console.ReadLine());
for (int i = 0; i < Q; i++)
{
tokens = Console.ReadLine().Split(' ');
int a, b, c;
a = int.Parse(tokens[0]);
b = int.Parse(tokens[1]);
if (a == 1)
{
c = int.Parse(tokens[2]);
if (c > 10) ok = false;
}
else c = 0;
queries.Add(new Querie(a, b, c));
}
if(ok)
{
Solve(Q, N);
return;
}
int q;
double log;
int f, r, prod;
for (int i = 0; i < Q; i++)
{
q = queries[i].a;
switch (q)
{
case 1:
p = queries[i].b;
f = queries[i].c;
if (p == 1)
{
A[p] = f;
Log[p] = Math.Log10(f);
continue;
}
prod = mult(inverse(A[p]), f);
log = Math.Log10(f) - Log[p];
foreach (int d in D[p])
{
R[d] = mult(R[d], prod);
L[d] += log;
}
A[p] = f;
Log[p] = Math.Log10(f);
break;
case 2:
r = queries[i].b;
sb.Append(firstDigit(L[r] + Log[1]) + " " + mult(R[r], A[1]) + "\n");
break;
default: break;
}
}
Console.Write(sb);
}
static void Solve(int Q, int N)
{
int q, p;
int f, r;
long ans;
for (int i = 0; i < Q; i++)
{
q = queries[i].a;
switch (q)
{
case 1:
p = queries[i].b;
f = queries[i].c;
A[p] = f;
break;
case 2:
r = queries[i].b;
ans = 1;
for (int j = 1; j <= N; j += r) ans *= A[j];
Console.WriteLine(firstDigit(Math.Log10(ans)) + " " + (ans % mod));
break;
default: break;
}
}
}
static int mult(int a, int b)
{
long t = 1L* a * b;
if (t >= mod) t %= mod;
return (int)t;
}
static int modPow(int b, int e)
{
int ans = 1;
while(e > 0)
{
if (e%2 == 1) ans = mult(ans, b);
b = mult(b, b);
e >>= 1;
}
return ans;
}
static int inverse(int a)
{
return modPow(a, mod - 2);
}
static int firstDigit(double L)
{
double p = Math.Truncate(L);
double tp = Math.Pow(10.0, L - p);
int ans = String.Format("{0}", tp)[0] - '0';
return ans;
}
}
}Chef and cities CodeChef Solution Review:
In our experience, we suggest you solve this Chef and cities 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 cities CodeChef Solution.
Conclusion:
I hope this Chef and cities 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!
