Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Just a simple sum CodeChef Solution
Problem -Just a simple sum 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.
Just a simple sum CodeChef Solution in C++17
#include <iostream>
using namespace std;
long long power(long long a, long long n, long long m) {
long long ans = 1;
while (n > 0)
{
if (n%2 == 1) ans = (ans*a) % m;
a = (a*a) % m;
n /= 2;
}
return ans;
}
long long sum(long long x, long long q, long long m )
{
if (q == -1) return 0;
if (q%2 == 1)
return (1+x)*sum(x*x%m, (q-1)/2, m) % m;
else
return (1 + x*sum(x, q-1, m)) % m;
}
int main () {
int t;
cin>>t;
while (t--)
{
long long n, m;
cin>>n;
cin>>m;
long long q = n / m,ans = 0;
for (int i = 1; i <= m-1; i++)
{
long long a,b;
a = power(i, i, m);
b = power(i, m, m);
///cout<<a<<" "<<b<<endl;
if (i<=n%m)
ans = (ans + a*sum(b, q, m)) % m;
else
ans = (ans + a*sum(b, q-1, m)) % m;
}
cout<<ans<<endl;
}
return 0;
}Just a simple sum CodeChef Solution in C++14
#include <iostream>
using namespace std;
long long power(long long a, long long n, long long m) {
long long ans = 1;
while (n > 0)
{
if (n%2 == 1) ans = (ans*a) % m;
a = (a*a) % m;
n /= 2;
}
return ans;
}
long long sum(long long x, long long q, long long m )
{
if (q == -1) return 0;
if (q%2 == 1)
return (1+x)*sum(x*x%m, (q-1)/2, m) % m;
else
return (1 + x*sum(x, q-1, m)) % m;
}
int main () {
int t;
cin>>t;
while (t--)
{
long long n, m;
cin>>n;
cin>>m;
long long q = n / m,ans = 0;
for (int i = 1; i <= m-1; i++)
{
long long a,b;
a = power(i, i, m);
b = power(i, m, m);
///cout<<a<<" "<<b<<endl;
if (i<=n%m)
ans = (ans + a*sum(b, q, m)) % m;
else
ans = (ans + a*sum(b, q-1, m)) % m;
}
cout<<ans<<endl;
}
return 0;
}Just a simple sum CodeChef Solution in PYTH 3
def S(a, n, m):
if n == -1: return 0
if n == 0: return 1
if n == 1: return (1 + a) % m
if n % 2 == 1:
ans = (1 + a) * S(a * a % m, (n - 1)//2, m)
else:
ans = 1 + a * (1 + a) * S(a * a % m, n//2 - 1, m)
return ans % m
for _ in range(int(input())):
n,m = map(int,input().split(' '))
s=0
e = n//m
for i in range(1,n%m+1):
f = pow(i,e*m + i,m)
s += f
s = s%m
for i in range(2,m+1):
a = pow(i,m,m)
d = S(a,e-1,m)
b = pow(i,i,m)
s += ((d%m)*b)%m
s = s%m
s += e
print(s%m) Just a simple sum CodeChef Solution in C
#include <stdio.h>
int powmod(int a, long long n, int m)
{
long long s=a,t=1;
while(n)
{
if (n&1)
t=(t*s)%m;
s=(s*s)%m;
n/=2;
}
return t;
}
int inv(long long x, int y)
{
int yy=y;
long long p0=1,p1=0,t,p2;
while(y)
{
p2=p0-x/y*p1;
p0=p1;
p1=p2;
t=y;
y=x%y;
x=t;
}
p0%=yy;
if (p0<0)
return p0+yy;
return (int) p0;
}
int kineski(int *a, int *b, int n, long long m)
{
int i;
long long ukupno=0;
for(i=0;i<n;i++)
ukupno+=(m/b[i]*a[i]*inv(m/b[i],b[i]))%m;
return (int)(ukupno%m);
}
long long ukupno;
int elem[100],ost[100];
int koliko;
int i,a,p,m,t,mm;
long long n;
long long temp1,temp2,temp3;
int u,k;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld %d",&n,&m);
mm=m;
koliko=0;
for(p=2;m>1;p++)
{
if (p*p>m)
p=m;
if (m%p==0)
{
u=1;a=0;
while(m%p==0)
{
m/=p;
u*=p;
a++;
}
elem[koliko]=u;
ukupno=0;
for(k=1;k*p<a&&k*p<=n;k++)
ukupno+=powmod(k*p,(long long)k*p,u);
ukupno%=u;
for(i=1;i<u&&i<=n;i++)
{
if (i%p==0)
continue;
temp1=powmod(i,(long long)i,u);
temp3=powmod(i,(long long)u,u);
if (temp3==1)
{
ukupno+=((n-i+u)/u*temp1)%u;
ukupno%=u;
continue;
}
temp3=inv(temp3-1,u);
temp2=powmod(i,(n-i+u)/u*u,u)-1;
ukupno+=(temp1*temp2*temp3)%u;
ukupno%=u;
}
ost[koliko++]=ukupno;
}
}
printf("%d\n",kineski(ost,elem,koliko,mm));
}
}Just a simple sum CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.io.PrintWriter;
import java.util.Locale;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Locale.setDefault(Locale.US);
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out,true);
int N = in.nextInt();
for (int ii=0; ii<N; ii++) {
long n = in.nextLong();
int m = in.nextInt();
if (m == 1) {
out.println(0);
continue;
}
int lim = (int)Math.sqrt(m);
long partial = 0;
long partialm = 0;
for (int i=0; primes[i]<=lim; i++) {
int pk = 1;
while (m%primes[i]==0) {
pk *= primes[i];
m /= primes[i];
}
if (pk > 1) {
long r = primepower(n, pk);
if (partialm == 0) {
partialm = pk;
partial = r;
} else {
partial = merge(r*partialm, partialm, partial*pk, pk);
partialm *= pk;
}
}
}
if (m > 1) {
long r = primepower(n, m);
if (partialm == 0) {
partial = r;
partialm = m;
} else {
partial = merge(r*partialm, partialm, partial*m, m);
partialm *= m;
}
}
partial = partial%partialm;
if (partial < 0) {
partial += partialm;
}
out.println(partial);
}
out.close();
}
static long modpow(long base, long exponent, long modulus) {
long result = 1;
while (exponent > 0) {
if ((exponent&1) == 1) {
result = (result*base)%modulus;
}
exponent >>= 1;
base = (base*base)%modulus;
}
return result;
}
static int[] primes = new int[] {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,
211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,
307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,
401,409,419,421,431,433,439,443,449
};
static long phi(int n) {
long result = 1;
int lim = (int)Math.sqrt(n);
for (int i=0; primes[i]<=lim; i++) {
int pk = 1;
while (n%primes[i] == 0) {
pk*=primes[i];
n/=primes[i];
}
if (pk != 1) {
result *= (pk/primes[i])*(primes[i]-1);
}
}
if (n>1) {
result *= n-1;
}
return result;
}
static long merge(long r1, long m1, long r2, long m2) {
if (m2==0) {
return r1;
} else {
long newm = m1%m2;
return merge(r2,m2,r1-r2*(m1/m2), newm);
}
}
static long primepower(long n, long m) {
long sum = 0;
long q = n/m;
long r = n%m;
for (int i=1; i<m; i++) {
long val;
long x = (i<=r) ? q : (q-1);
if (x<0) break;
long div = modpow(i,m,m)-1;
val = modpow(i, i, m);
if ((i==1) || (div==0)) {
val = val*(x+1);
} else {
if (val != 0) {
long zum = modpow(i, m*(x+1), m)-1;
long gcd = gcd(div,m);
long d = div/gcd;
zum /= gcd;
int newm = (int)(m/gcd);
long invd = modpow(d, phi(newm)-1, newm);
zum = (zum*invd)%m;
val = (val*zum)%m;
}
}
sum = (sum+val)%m;
}
return sum;
}
static long gcd(long a, long b) {
if (b==0) {
return a;
} else {
return gcd(b,a%b);
}
}
}Just a simple sum CodeChef Solution in PYTH
# cook your code here
import numpy as np
import sys
sys.setrecursionlimit(1000*1000*1000)
def gpsum(k,r,mod):
if r == 1:
return (k)%mod
if k ==1:
return 1
num = (pow(r,k,mod*(r-1))-1)%(mod*(r-1))
return (num/(r-1))%mod
# def sum_mod( x, k, m)
# if (k == 1):
# return 1;
# if (k%2 == 0)
# return (1+x)*sum_mod(x*x%m, k/2, m) % m;
# return (1 + x*sum_mod(x, k-1, m)) % m;
# def gpsum(a,k,r,mod):
# return a*sum_mod(r,k,mod)
# pass
T = int(raw_input())
for _ in range(T):
N,M = map(int,raw_input().strip('\n').split(' '))
mod = M
ans = 0
if 1:
for i in range(1,min(N+1,M)):
ki = int((N-i)/M)+1
ai = pow(i,i,mod)
ri = pow(i,mod,mod)
# print i, gpsum(ai,ki,ri,mod)%mod
ans += (ai*gpsum(ki,ri,mod))%mod
print ans%mod
# brute = False
# if brute:
# ans = 0
# for i in range(1,N+1):
# ans += pow(i,i,mod)
# ans %= mod
# # print ans
# print 'brute', ansJust a simple sum CodeChef Solution in C#
using System;
namespace ConsoleApplication12
{
/*
* 1) set a = k * m + t , t = a%m;
* (a^b) % m = ((k*m+t)^b) % m = (t^b) % m;
*
* 2) (1^1 + 2^2 + ... + N^N)%M
* = (1^1 + 1^(M+1) + 1^(2M+1) + ... )%M
* +(2^2 + 2^(M+2) + 2^(2M+2) + ... )%M
* + ...
* +((M-1)^(M-1) + (M-1)^(2M-1) + (M-1)^(3M-1) + ... + )%M
*
* 3) set a = X^X, q = X^M , s = (N - X)/M; where N >= X, X<M;
*
* 4) (a/b) %m = (a%bm)/b
*
* 5) a*q^0 + a*q^1 + a*q^2 + ... + a*q^s = a * [q^(s+1)-1]/(q-1)
*
* 6) consider some value great than long.MaxValue
*
*
*/
class CaseItem
{
int caseIndex;
long n;
int m;
public CaseItem(int index)
{
caseIndex = index;
string s = System.Console.ReadLine();
string[] a = s.Split(' ');
n = long.Parse(a[0]);
m = int.Parse(a[1]);
}
private long cal_series(long n, int m, int si)
{
long a = QuickPower_short(si, si, m);
long q = QuickPower_short(si, m, m);
if (q == 0)
{
return a;
}
long s = (n - si) / m + 1;
if (q == 1)
{
return (a * (s % m)) % m;
}
long m2 = (q - 1) * m;
long sum = QuickPower(q, s, m2);
sum = (sum + m2 - 1) % m2;
sum = (sum * a) % m2;
return sum / (q - 1);
}
public void Execute()
{
long total = 0;
for (int _base = 1; _base < m && _base <= n; _base++)
{
long series_num = cal_series(n, m, _base);
total += series_num;
}
total %= m;
Console.WriteLine(total.ToString());
}
private long multi(long x, long y, long mod)
{
//if (y == 0)
//{
// return 0;
//}
//if (x <= long.MaxValue / y)
//{
// return (x * y) % mod;
//}
//else
if (x >= y)
{
// long x1 = (long)Math.Floor(Math.Sqrt(x));
// long x2 = x - x1 * x1;
long x1 = 65536;
long x2 = x >> 16;
long x3 = x % x1;
// return (multi(multi(x1, y, mod), x1, mod) + multi(x2, y, mod)) % mod;
// return (multi(x1, y, mod) * x1 + x2 * y) % mod;
return (((y << 16) % mod) * x2 + x3 * y) % mod;
}
else
{
// return multi(y, x, mod);
// long y1 = (long)Math.Floor(Math.Sqrt(y));
// long y2 = y - y1 * y1;
long y1 = 65536;
long y2 = y >> 16;
long y3 = y % y1;
// return (multi(multi(x1, y, mod), x1, mod) + multi(x2, y, mod)) % mod;
// return (multi(x, y1, mod) * y1 + x * y2) % mod;
return (((x << 16) % mod) * y2 + x * y3) % mod;
}
}
private long QuickPower_short(long x, long n, long mod)
{
long power = 1;
while (n > 0)
{
if ((n & 1) == 1)
{
power = (power * x) % mod;
}
x = (x * x) % mod;
n >>= 1;
}
return power;
}
private long QuickPower(long x, long n, long mod)
{
long power = 1;
while (n > 0)
{
if ((n & 1) == 1)
{
if (power <= long.MaxValue / x)
{
// power = (power * x) % mod;
power *= x;
power %= mod;
}
else
{
power = multi(power, x, mod);
}
}
if (x <= long.MaxValue / x)
{
x *= x;
x %= mod;
}
else
{
x = multi(x, x, mod);
}
n >>= 1;
}
return power;
}
}
class Round
{
int case_num;
CaseItem[] items;
public Round()
{
case_num = int.Parse(Console.ReadLine());
items = new CaseItem[case_num];
for (int i = 0; i < case_num; i++)
{
items[i] = new CaseItem(i + 1);
}
}
public void Execute()
{
foreach (CaseItem item in items)
{
item.Execute();
}
}
}
class Program
{
static void Main(string[] args)
{
(new Round()).Execute();
// Debug();
}
static void Debug()
{
System.IO.TextReader stdin = System.Console.In;
System.IO.TextWriter stdout = System.Console.Out;
try
{
using (System.IO.StreamReader reader = new System.IO.StreamReader("a.in"))
{
using (System.IO.StreamWriter writer = new System.IO.StreamWriter("out.txt"))
{
long datetime1 = DateTime.Now.Ticks;
System.Console.SetIn(reader);
System.Console.SetOut(writer);
(new Round()).Execute();
long datetime2 = DateTime.Now.Ticks;
DateTime datetime3 = DateTime.Now;
long seconds = (datetime2 - datetime1) / (datetime3.AddSeconds(1).Ticks - datetime3.Ticks);
System.Console.WriteLine(" second is : " + seconds.ToString());
}
}
}
finally
{
System.Console.SetIn(stdin);
System.Console.SetOut(stdout);
}
}
}
}Just a simple sum CodeChef Solution Review:
In our experience, we suggest you solve this Just a simple sum 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 Just a simple sum CodeChef Solution.
Conclusion:
I hope this Just a simple sum 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!
