Help needed with a problem

Revision en1, by Jovan26, 2019-09-18 00:41:02

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=add(sub,-1,c); long long temp=add(a,-1,c); long long inverse=power(temp,add(c,-2,c),c); sub=(sub*a)%c; sub=(sub*inverse)%c; rez=add(rez,-sub,c); cout << rez << '\n'; cin >> x >> a >> n >> c; } else { x=add(x,-n,c); 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)