Jovan26's blog

By Jovan26, history, 5 weeks ago, In English,

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;
}
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jovan26 (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I've checked the judge input with the following code:

char *ptr = NULL;
...
if( !isPrime( c ) ) *ptr = '\0';

and I've got RE. So not all c's in the judge input are prime values. You can try other approaches.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it now. Thank you very much for the help.