codeshark problemA

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
typedef vector<int> vi;
typedef complex<double> point;
template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
const int maxn = 1975296 + 100;
bool prime[maxn];
int phi[maxn], lambda[maxn];
vi v[maxn];
int mark[maxn];
int mod;
inline int power(int a, int b,int n){
    if(!b)  return 1;
    int c = power(a, b/2, n);
    c = (1LL * c * c)%n;
    if(b % 2)
        c = (1LL * c * a)%n;
    return c;
}
inline int solve(int n){
    ll ans = 0LL;
    memset(mark,0,sizeof mark);
    vi v;
    int m = lambda[n];
    for(int i = 1;i * i <= m;i ++)if(m % i == 0){
        v.pb(i);
        if((m/i) > i)
            v.pb(m/i);
    }
    sort(all(v));
    For(p,1,n){
        if(__gcd(p, n) == 1){
            rep(c, v)
                if(power(p, c, n) == 1){
                    ans = (ans + c);
                    break;
                }
        }
        else{
            int cur = p;
            while(cur && mark[cur] != p){
                mark[cur] = p;
                ans = (ans + 1LL);
                cur = (1LL * cur * p)%n;
            }
        }
    }
    return ans;
}
int sum[maxn];
main(){
    cin >> mod; //  reading your delta
    fill(prime+2,prime+maxn,true);
    For(i,1,maxn){
        phi[i] += i;
        if(prime[i])
                v[i].pb(i);
        for(int j = i + i;j < maxn;j += i){
            phi[j] -= phi[i];
            if(prime[i])
                prime[j] = false, v[j].pb(i);
        }
    }
    For(i,2,maxn){
        lambda[i] = 1;
        int k;
        if(v[i].size() == 1){
            if(v[i][0] == 2){
                if(i == 2 or i == 4)
                    lambda[i] = phi[i];
                else
                    lambda[i] = phi[i]/2;
            }
            else
                lambda[i] = phi[i];
        }
        else{
            int j = i;
            rep(p, v[i]){
                int x = 1;
                while(j % p == 0){
                    j /= p;
                    x *= p;
                }
                x = lambda[x];
                k = __gcd(x, lambda[i]);
                x/=k;
                lambda[i] *= x;

            }
        }
    }
    For(i,0,maxn){
        int x = (1LL * lambda[i] * lambda[i]);
        sum[i] =(1LL * sum[i-1] + x);
    }
    cout << solve(1234) % mod << '\n' <<
    solve(1111151) % mod << '\n' <<
    solve(1234567) % mod << '\n' <<
    sum[1234] % mod << '\n' <<
    sum[12345] % mod<< '\n'<<
    sum[1234567] % mod<< endl;
}