[競プロ]for文のカウンタをlong longにしたら何が変わるのか。

Question

ABC169 D問題

この問題の解説放送にて、for文中のカウンタiをint型ではなく、long longに書き換える場面がありました。
実際にその部分をintに変えて提出したらTLEが出て、long longに直すとACされました。

for文のカウンタの型をlong longにすると、どういう変化が起きて処理速度が変わるのでしょうか。
毎回long longにしてもいいですが、何となく必要なとき以外はintにしたいので理由が知りたいです。

よろしくお願いします。
一応、以下が参考コードになります。

#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n;
  cin>>n;
  int z;
  int a=0;
  for(long long i=2;i*i<=n;++i){
    int c=0;
    while(n%i==0){
      n/=i;
      c++;
    }
    for(int j=1;c>0;++j,c-=j){
      a++;
    }
  }
  if(n!=1)a++;
  cout<<a;
}

Answer 1

for文のカウンタの型をlong longにすると、どういう変化が起きて処理速度が変わるのでしょうか。

処理速度の問題ではありません。int型では10の12乗という値は大きすぎて、オーバーフローする環境が多いです。結果、条件判定もおかしくなって、無限ループに陥っているものと思われます。

Comments

[maisumakun]

intが32ビットの環境では、入れられる値は21億ちょっとが限界です。

[jamboc]

ご回答ありがとうございます！

シンプルに値の大きさの問題だったのですね。
WAが一つもなかったので、そういった類ではなく処理速度が関係しているものと思ってしまいました。

[maisumakun]

無限ループしたために、出力結果を云々する以前に制限時間を使い果たしてしまった形です。

Answer 2

前の人が既にオーバーフローと答えていますが、補足です。

何となく必要なとき以外はintにしたい

であれば、以下まで絞り込めます。
要は、i*iでオーバーフローするだけなので、ここだけlong longにキャストすれば良いです。

  for (int i=2; (long long)(i)*i <= n; ++i){

あと、ルートを取っておく方法もありますが、sqrtは浮動小数点を使いますし、
doubleは誤差が怖いです(10**12でdoubleなら大丈夫な気もします)

  const int sqn = (int)sqrt(n);
  for (int i=2; i <= sqn; ++i){