Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Help needed with a problem

Revision en2, by Jovan26, 2019-09-18 00:42:03

I tried to solve this problem and when I tested my code on the test cases provided here I got all correct answers, but when I tried to submit it I got wrong answer. My idea was to calculate (a^n)*x-(a^n+a^(n-1)+...+a^2+a) mod c, where I would calculate (a^n+a^(n-1)+...+a^2+a) using the formula for the sum of a geometric sequence. I also put a special case if a%c==1 where the answer is (x-n)%c. I also tried using endl instead of '\n' and putting the answers in a vector and printing them afterwards but it didn't accomplish anything. This is my first blog so sorry if I made any mistakes and thanks in advance for your help.

#include <bits/stdc++.h>

using namespace std;
long long add(long long i,long long j,long long mod)
{
if(i+j<0)
{
int tmp=0;
while(i+j+tmp<0)tmp+=mod;
return i+j+tmp;
}
if(i+j>=mod)
{
int tmp=0;
while(i+j-tmp>=mod)tmp+=mod;
return i+j-tmp;
}
return i+j;
}
long long power(long long n,long long k,long long mod)
{
n%=mod;
long long rez=1;
while(k)
{
if(k&1)
{
rez=(rez*n)%mod;
}
n=(n*n)%mod;
k>>=1;
}
return rez;
}
int main()
{
ios_base::sync_with_stdio(false);
long long x,a,n,c;
cin >> x >> a >> n >> c;
while(x!=0 || a!=0 || n!=0 || c!=0)
{
if(a%c!=1)
{
long long rez=power(a,n,c);
rez=(rez*x)%c;
long long sub=power(a,n,c);
sub=(sub*a)%c;
sub=(sub*inverse)%c;
cout << rez << '\n';
cin >> x >> a >> n >> c;
}
else
{
cout << x <<'\n';
cin >> x >> a >> n >> c;
}
}
return 0;
}


#### History

Revisions Rev. Lang. By When Δ Comment
en2 Jovan26 2019-09-18 00:42:03 4
en1 Jovan26 2019-09-18 00:41:02 2139 Initial revision (published)