Why is this STFM solution wrong?

general
1

Basically each time i calculate i*i if it is not already calculated and then i multiple with the rest of the integers that have already been computed until now.

#include <stdio.h>
#include <iostream>
using namespace std;
 
int fact[10000000] = {0};
int getfactsum(int integer,int m){
    long long int prevsum = 1;
    long long int answer = 1;
    for(int i = 2;i<=integer;i++){
        unsigned long long int val;
        if(fact[i] == 0){
            val = (i * i) % m;
            fact[i]  = val;
        }
        else
            val = fact[i];
 
        val = (val * prevsum) % m;
        answer = (answer + val) % m;
        prevsum = (prevsum * i) % m;
    }
    return answer % m;
}
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    long long int answer =0;
    for(int i = 0;i < n;i++){
        long long int next;
        scanf("%lld",&next);
        next = next % m;
        unsigned long long int sum = next * ((next * (1 + next)) >> 1);
        unsigned long long int factsum = getfactsum(next,m);
        answer += ((sum % m) + factsum) % m;
    }
    printf("%d\n",answer % m);
}
2

(next * (next+1)/2)%m is not the same as (next%m)*(next%m+1)/2.
Instead of taking mod of next, check which of next and (next+1) is even and divide, as is mentioned in the editorial. :slight_smile: