304 North Cardinal St.
Dorchester Center, MA 02124

# Chef and cities CodeChef Solution

## 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;

{
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] << " ";

}
}

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
{
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)
{
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]);
}

}
}
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte [] buffer;

din = new DataInputStream (System.in);
buffer = new byte[BUFFER_SIZE];
}

public Reader (String file_name) throws IOException {
din = new DataInputStream (new FileInputStream (file_name));
buffer = new byte[BUFFER_SIZE];
}

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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
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 {
buffer[0] = -1;
}

private byte read () throws IOException {
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

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 friendliness``````

## Chef 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;
if (N > 10) ok = false;

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)
{
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;
}
}

for (int i = 0; i < Q; i++)
{
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;
}

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.

Find on CodeChef

##### 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!