In ALATE problem ,my solution got AC for first subtask and TLE for second subtask,i modified it and now
#include
#define MAX 1000000007
long long func(long long A[],int x,int N)
{
long long sum = 0;
int i;
//printf("n is %d and x is %d\n",N,x);
for(i=x;i<=N;i+=x)
{
sum = ((sum + (A[i]*A[i])%MAX)%MAX);
}
return sum;
}
int main()
{
int n,i;
scanf("%d",&n);
long long a[1000001];
for(i=0;i<n;i++)
{
int y,z,j,b,c,d;
long long e;
scanf("%d %d",&y,&z);
for(j=0;j<y;j++)
{
scanf("%lld",&a[j+1]);
}
long long sum[10];
//printf("here\n");
for(j=1;j<y && j<8;j++)
{
sum[j] = func(a,j,y);
}
for(j=0;j<z;j++)
{
scanf("%d %d",&b,&c);
if(b == 1)
{
if(c <= 1)
{
printf("%lld\n",sum[c]);
}
else
{
printf("%lld\n",func(a,c,y));
}
}
else
{
scanf("%lld",&e);
int k;
sum[1] = (sum[1] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
if( c % 2 == 0)
{
sum[2] = (sum[2] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
if(c%3 == 0)
{
sum[3] = (sum[3] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
if(c%4 == 0)
{
sum[4] = (sum[4] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
if(c%5 == 0)
{
sum[5] = (sum[5] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
if(c%6 == 0)
{
sum[6] = (sum[6] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
if(c%7 == 0)
{
sum[7] = (sum[7] - (a[c]*a[c])%MAX + (e*e)%MAX)%MAX;
}
a[c] = e;
}
}
}
return 0;
}`enter code here`
what is the problem in this,it gives wrong answer
Clearly, you are applying brute force and it won’t fetch you full points, the problem lies in when you are updating.
To solve this question, ALATE from August Loc you need to do some precomputation so as to fit the answer in specified time-limit.
Since “func” calculates the sum of a given index x and all it’s multiple in the given array(squares). So we can precompute all the values for x.
for(i=1;i<=n;i++)
{
s=0;
for(j=i;j<=n;j+=i){
s = ( s + (arr[i]*arr[i]) % 1000000007) % 1000000007 ;
}
sum[i] = s ;
}
Since you have all the pre-computed values than your query of type 1 can be answered in O(1) but the problem arises in the update query for that you need to know which values are actually going to be affected by the change of that particular x. (this is also pre-computed) so whenever a query of 2nd type occurs than you have to iterate over the values of sum[i] which are going to be affected and update their new values which are sum[i]-arr[i]*arr[i]+newValue *newValue;
First, we will pre-compute which are going to affect by the index x.
vector v[100001];
for(ii=1;ii<100001;ii++) {
for(jj=ii;jj<100001;jj+=ii)
v[jj].push_back(ii); }
After that we just need to iterate over the affected values and update them as they are stored in v[x]
for(i=0;i<v[x].size();i++)
{
sum[v[x][i]] = (sum[v[x][i]] - sq[x] +
nsq+1000000007) %1000000007 ;
}
where nsq is new square value.
Hope this helps!
(
[1])
[1]: https://www.codechef.com/viewsolution/15155591
@sandeep_007 it will be helpful for me if you check my solution !
even i had updated for query 2
https://www.codechef.com/viewsolution/15134001
i have done the same i guess.
my code does’t take much time,but the problem is why is it giving WA,i am updating everytime a new value comes , like i changed sum[1] = (sum[1] - (a[c]a[c])%MAX + (ee)%MAX)%MAX;
and i check if c%k == 0 then i update sum[c] too.
but only 8 values? what if I enter 9.
see, the set of values changed by changing any particular value of x will be large and not just limited to 1,2 … 7, for example A= [1 2 3 4] than sqA = [1+4+9+16,4+16,9,16] now assuming you have a query of type 2 in which you have to change third element to 5 (now A[2] == 5, 0 base index) so now sqA = [1+4+25-9+16,4+16,25,16] not just 2%2 == 0, the 0 index. hope this helps