我碰到了一道题，题目要求 $(\sum^n_{i=1} ia^i) mod \ p$

同时有T组数据，数据范围a,n,p是10e9，T是10e5

想问下各位大佬思路，用快速幂答案总是不对...

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;

u64 qpow(int a,int b,int p){
    u64 res=1;
    for(;b;b>>=1){
        if(b&1) res=res*a%p;
        a=a*a%p;
    }
    return res;
}

void solve(){
    int n,a,p;
    scanf("%d%d%d",&n,&a,&p);
    u64 res=0;
    for(int i=1;i<=n;i++){
        res+=(i*qpow(a,i,p))%p;
        res=res%p;
        printf("==%lld\n",res);
    }
    printf("%lld\n",res%p);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
}

输入

4
928 263217362 918273612
817 18276362 728192763
827162521 1 726152738
716253712 1 91827321

输出

28467122
151221515
514235435
62627836

感谢各位大佬