結果
問題 | No.278 連続する整数の和(2) |
ユーザー |
|
提出日時 | 2016-05-18 20:20:32 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 3,244 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 81,012 KB |
実行使用メモリ | 47,344 KB |
最終ジャッジ日時 | 2024-12-23 09:11:42 |
合計ジャッジ時間 | 7,269 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
package yukicoder;import java.math.BigInteger;import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;public class Main{public static void main(String[] args){new Main().solve();}void solve(){Scanner sc=new Scanner(System.in);long n=sc.nextLong();long x=0;if(n%2==0){x=n/2;}else{x=n;}Prime ps=new Prime(2*1000_000_000_000L);long sum=sum_d(ps.primeFactorF(x));System.out.println(sum);/** 連続するN個の正整数の和を一般に割る最大値を求めよ。** 1からMまでの和は(1/2)M(M+1)* 1からM+Nまでの和は(1/2)(M+N)(M+N+1)* M+1からM+Nまでの和は* (1/2)( (M+N)(M+N+1) - M(M+1) )* =(1/2)N( 2M + N + 1 )* i)N=2kと書けるとき* =k(2M+2k+1)* ii)N=2k-1と書けるとき* =N(M+k)*/}class Prime{long n;ArrayList<Integer> ps=new ArrayList<Integer>();Prime(long n){this.n=n;ps=primeList((int)Math.sqrt(n));}boolean[] isPrimeArray(int max){boolean[] isPrime=new boolean[max+1];Arrays.fill(isPrime, true);isPrime[0]=isPrime[1]=false;for(int i=2;i*i<=max;i++){if(isPrime[i]){for(int j=2;j*i<=max;j++){isPrime[j*i]=false;}}}return isPrime;}/** max以下の素数のリストを返す*/ArrayList<Integer> primeList(int max){boolean[] isPrime=isPrimeArray(max);ArrayList<Integer> primeList=new ArrayList<Integer>();for(int i=2;i<=max;i++){if(isPrime[i]){primeList.add(i);}}return primeList;}/** numをprimeListの素数をもとに素因数分解し、因数を* ArrayList<Factor>の形で返す。1は含まれない。* primeListにはnumの平方根以下の素数が含まれていなければならない。**/ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList,long num){ArrayList<Factor> ret=new ArrayList<Factor>();for(int p:primeList){int exp=0;while(num%p==0){num/=p;exp++;}if(exp>0)ret.add(new Factor(p,exp));}if(num>1)ret.add(new Factor(num,1));return ret;}ArrayList<Factor> primeFactorF(long num){ArrayList<Factor> ret=new ArrayList<Factor>();for(int p:ps){int exp=0;while(num%p==0){num/=p;exp++;}if(exp>0)ret.add(new Factor(p,exp));}if(num>1)ret.add(new Factor(num,1));return ret;}}class Factor{long base,exp;Factor(long base,long exp){this.base=base;this.exp=exp;}}/** 戻り値:約数の和*/long sum_d(ArrayList<Factor> fs){long sum=1;for(Factor f:fs){sum*=Long.parseLong((BigInteger.ONE.subtract(pow_big(f.base,f.exp+1))).divide(BigInteger.ONE.subtract(BigInteger.valueOf(f.base))).toString());}return sum;}BigInteger pow_big(long a,long n){BigInteger A=new BigInteger(String.valueOf(a));BigInteger ans=BigInteger.ONE;while(n>=1){if(n%2==0){A=A.multiply(A);n/=2;}else if(n%2==1){ans=ans.multiply(A);n--;}}return ans;}long pow(long a,long n){long A=a;long ans=1;while(n>=1){if(n%2==0){A=A*A;n/=2;}else if(n%2==1){ans=ans*A;n--;}}return ans;}}