結果
問題 | No.278 連続する整数の和(2) |
ユーザー |
![]() |
提出日時 | 2015-09-08 12:50:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,288 bytes |
コンパイル時間 | 1,478 ms |
コンパイル使用メモリ | 165,784 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:54:44 |
合計ジャッジ時間 | 2,227 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 WA * 4 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef unsigned long long int ull;ull calc(ull a,ull b){ull ans=1;while(b>0){if(b%2) ans*=a;a*=a;b/=2;}return ans;}int main(){ull n; cin>>n;if(n<3){cout<<1<<endl;return 0;}/*n以上の素数xを使ってn個の連続する自然数の和は* x(n+n*(n-1)/2)と表せる。よってnとn*(n-1)/2の最大公約数をgとおき、* g = a^s * b^t *c^u と素因数分解できたとすると* Σx=(a^0+a^1...+a^s)*(b^0+b^1...+b^t)*(c^0+c^1...+c^u)* =(a^(s+1)-1)/a-1*。* ここで、n*(n-1)/2は64bit型に収まらないので、場合分け。* 1.(n-1)が偶数のとき nで括ってxn(1+(n-1)/2)。g=n。* 2.nが偶数のとき n/2で括ってxn/2(2+(n-1))。n-1は奇数だからg=n/2。* あとは適当に因数分解の結果をmapなどに放っておけば解ける?* (答えが64bitに収まるかは知らない)*/ull g,cp;if(n%2==0) g=n/2;else g=n;cp=g;map<ull,ull> ap;for(ull i=2;i*i<=g;i++){while(g%i==0) ap[i]++,g/=i;}if(ap.size()==0){cout<<cp+1<<endl;return 0;}if(g!=1) ap[g]++;ull ans=1;for(auto it=ap.begin();it!=ap.end();it++){ull a=it->first,s=it->second;ans*=(calc(a,s+1)-1)/(a-1);}cout<<ans<<endl;return 0;}