まず、 \(i\) 日目にいくらの悲しみが増加するかを求めましょう。 \(i\) 日目に使用すべき商品券の枚数は \(ceil((A \times i)/M)\) ( \(ceil\) は小数点以下切り上げ) です。

解法1: 問題を観察して解く

サンプルの説明文を延長してみましょう。

• \(1\) 日目には \(5\) 円のリンゴを買います。 \(8\) 円の商品券は \(1\) 枚必要で、このとき高橋君の「悲しさ」は \(3\) 増加します。
• \(2\) 日目には \(10\) 円のリンゴを買います。 \(8\) 円の商品券は \(2\) 枚必要で、このとき高橋君の「悲しさ」は \(6\) 増加します。
• \(3\) 日目には \(15\) 円のリンゴを買います。 \(8\) 円の商品券は \(2\) 枚必要で、このとき高橋君の「悲しさ」は \(1\) 増加します。
• \(4\) 日目には \(20\) 円のリンゴを買います。 \(8\) 円の商品券は \(3\) 枚必要で、このとき高橋君の「悲しさ」は \(4\) 増加します。
• \(5\) 日目には \(25\) 円のリンゴを買います。 \(8\) 円の商品券は \(4\) 枚必要で、このとき高橋君の「悲しさ」は \(7\) 増加します。
• \(6\) 日目には \(30\) 円のリンゴを買います。 \(8\) 円の商品券は \(4\) 枚必要で、このとき高橋君の「悲しさ」は \(2\) 増加します。
• \(7\) 日目には \(35\) 円のリンゴを買います。 \(8\) 円の商品券は \(5\) 枚必要で、このとき高橋君の「悲しさ」は \(5\) 増加します。
• \(8\) 日目には \(40\) 円のリンゴを買います。 \(8\) 円の商品券は \(5\) 枚必要で、このとき高橋君の「悲しさ」は \(0\) 増加します。
• \(9\) 日目には \(45\) 円のリンゴを買います。 \(8\) 円の商品券は \(6\) 枚必要で、このとき高橋君の「悲しさ」は \(3\) 増加します。
• \(10\) 日目には \(50\) 円のリンゴを買います。 \(8\) 円の商品券は \(7\) 枚必要で、このとき高橋君の「悲しさ」は \(6\) 増加します。
• \(\dots\)

高橋君の悲しさの増加量が \(8\) 日ごとに周期的に繰り返していることが予想できます。
実際この予想は正しく、一般には \(M\) 日ごとに高橋君の悲しさの増加量は繰り返します(\(i\) 日目と \(i+M\) 日目の悲しさの増加量が全ての \(i\) について一致する)。

証明:
\(i\) 日目に使うべき商品券の枚数を \(k\) 、 \(i\) 日目に増えた悲しさを \(s\) とします。
\(k \times M - A \times i = s\) (ここで、 \(0 \le s < M\) であり、 \(k\) は必要最低限の値であることに注意します)
\(k \times M + A \times M - A \times i - A \times M = s\)
\((k + A) \times M - A \times (i + M) = s\)
と式変形することができ、この式より \((i+M)\) 日目に使うべき商品券の最小枚数は \((k+A)\) 枚、この時増える悲しさは \(s\) であることが言えます。

今回の問題では \(M \le 300\) です。なので、 \(1,2,\dots,M\) 日目について増加する悲しさを並べてできた数列を繰り返した数列を \(N\) 項目まで足し合わせた値を求めればこの問題を解くことができます。計算量は \(O(TM)\) なので、実行時間制限にも間に合います。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

long long llceil(long long a,long long b){
  if(a%b==0){return a/b;}
  return (a/b)+1;
}

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,a,m;
    cin >> n >> a >> m;
    long long sum=0;
    vector<long long> v(m+1,0);
    for(long long i=1;i<=m;i++){
      v[i]=llceil(a*i,m)*m-a*i;
      sum+=v[i];
    }
    long long res=sum*(n/m);
    for(long long i=1;i<=(n%m);i++){
      res+=v[i];
    }
    cout << res << "\n";
  }
  return 0;
}

解法2. 高度な解法

この問題の答えは、 \(\displaystyle \sum^{N}_{i=1} \left ( ceil((A \times i)/M) \times M - A \times i \right )\) です。
整理すると、 \(M \times \left ( \displaystyle \sum^{N}_{i=1} ceil((A \times i)/M) \right ) - A \times \displaystyle \frac{N\times(N+1)}{2}\) とできます。
この中で、 \(\displaystyle \sum^{N}_{i=1} ceil((A \times i)/M)\) を求めることが問題の本質です。 ceil_sum と呼びましょう。
よく練習されている方、ACLに詳しい方ならこれに似た問題を知っているはずです。
その問題とは Floor Sum です。 floor_sum と ceil_sum との違いは、小数点以下の処理が切り捨てか切り上げかだけの違いです。
では、 ceil_sum を floor_sum に帰着させていきましょう。
以下の式で \(ceil\) を \(floor\) に変換できることが知られています。
\(\displaystyle ceil \left ( \frac{p}{q} \right ) = floor \left ( \frac{p+(q-1)}{q} \right )\) ( \(p,q\) は正整数とする)
証明は、 \(p\) が \(q\) で割り切れる場合とそうでない場合とで分ければ容易です。
この式を利用すると、 ceil_sum を以下のように floor_sum に帰着することができます。

\(\displaystyle \sum^{N}_{i=1} ceil((A \times i)/M) = \displaystyle \sum^{N}_{i=1} floor((A \times i + (M-1))/M) = \displaystyle \sum^{N-1}_{i=0} floor((A \times i + (A+M-1))/M)\)

あとは、 ACL に実装された floor_sum を適用すればよいです。

UPD: 以下の記述は ACL の floor_sum の制約が変更される前に書かれたものであり、情報が古いです。 現状の制約 では一番下の実装例のコードを書いても制約違反しません。

ひとつ注意点があります。 floor_sum に帰着した後に ACL を用いる場合、 ACLの制約違反にならないように 注意しましょう。 floor_sum での \(A,B\) の値が \(M\) 以上にならないように調整する必要があります。

実装例(C++):

#include<bits/stdc++.h>
#include <atcoder/math>

using namespace std;
using namespace atcoder;

// Constraints: a>=0 && b>=0
long long ext_floor_sum(long long n,long long m,long long a,long long b){
  long long res=0;

  if(a>=m){
    long long q=a/m;
    res+=((n*(n-1))/2)*q;
    a%=m;
  }
  if(b>=m){
    long long q=b/m;
    res+=n*q;
    b%=m;
  }

  res+=floor_sum(n,m,a,b);
  return res;
}

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,a,m;
    cin >> n >> a >> m;
    long long b=a+m-1; // always positive
    long long res=ext_floor_sum(n,m,a,b)*m;
    res-=a*((n*(n+1))/2);
    cout << res << "\n";
  }
  return 0;
}

メモ: 先ほど ACL の制約違反にならないように注意しましょうとは言ったものの、実際には floor_sum を \(a,b\) が制約違反したまま使ったような以下のコードでも AC します。(ACL の実装でそのようなケースも対応されています。) しかし、制約違反した状態でライブラリを使う行為は決して安全ではないことに留意してください。
実装例(C++):

#include<bits/stdc++.h>
#include <atcoder/math>

using namespace std;
using namespace atcoder;

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,a,m;
    cin >> n >> a >> m;
    long long b=a+m-1; // always positive
    long long res=floor_sum(n,m,a,b)*m;
    res-=a*((n*(n+1))/2);
    cout << res << "\n";
  }
  return 0;
}