1 /* 2 本題屬于圓周追擊問題： 3 假設已知兩個圓周運動的物體的周期分別是a ,b, 設每隔時間t就會在同一條直線上 4 在同一條直線上的條件是 角度之差為 PI ! 5 那么就有方程 （2PI/a - 2PI/b）* t=PI 所以就有 t=ab/(2|a-b|); 6 如果有多個物體， 就會有多個t值，所以每隔 所有 t值的最小公倍數的時間所有的物體就會在同一直線上！ 7 8 另外：如果分數的分子分別是 a1, a2, ...., 和 b1, b2, .... 9 那么所有分數的最小公倍數就是lcm(a1, a2, ...)/gcd(b1, b2,....); 10 11 再有：如何求多個數的最小公倍數呢？ 12 根據數論，每一個數都可以表示成素數的乘積的形式！ 13 令p[i]存儲素數，將a1,a2,...分別整除以p[i]，直到除盡！并記錄除以每個p[i]時的個數temp; 14 并更新該個數的最大值cnt[i]=max(temp, cnt[i]); 15 16 最后cnt[i]個p[i]分別相乘得到最終的結果就是所有數的最小公倍數！ 17 */ 18 #include<iostream> 19 #include<cstring> 20 #include<cmath> 21 #include<cstdio> 22 #define M 10005 23 #define N 1005 24 using namespace std; 25 typedef long long LL; 26 LL p[M]; 27 bool isP[M]; 28 LL cnt[M]; 29 LL q[N]; 30 LL ans[N], endx; 31 LL top; 32 33 void bigN(){//大數據的處理 34 LL c=0; 35 endx=0; 36 ans[0]=1; 37 for(LL i=0; i<top; ++i) 38 for(LL j=0; j<cnt[i]; ++j){ 39 for(LL k=0; k<=endx; ++k){ 40 ans[k]=ans[k]*p[i] + c; 41 c=ans[k]/10000; 42 ans[k]%=10000; 43 } 44 if(c>0){ 45 ans[++endx]=c; 46 c=0; 47 } 48 } 49 } 50 51 void isPrime(){ 52 LL i, j; 53 isP[1]=1; 54 for(i=2; i<M; ++i){ 55 if(!isP[i]) p[top++]=i; 56 for(j=0; j<top && i*p[j]<M; ++j){ 57 isP[i*p[j]]=1; 58 if(i%p[j]==0) break; 59 } 60 } 61 } 62 63 void solve(LL k){ 64 for(LL i=0; i<top && p[i]<=k; ++i){ 65 LL tmp=0; 66 while(k%p[i]==0){ 67 ++tmp; 68 k/=p[i]; 69 } 70 71 if(tmp>cnt[i]) 72 cnt[i]=tmp; 73 } 74 } 75 76 LL gcd(LL a, LL b){ 77 while(b){ 78 LL r=a%b; 79 a=b; 80 b=r; 81 } 82 return a; 83 } 84 85 int main(){ 86 LL n; 87 isPrime(); 88 while(scanf("%lld", &n)!=EOF){ 89 memset(cnt, 0, sizeof(cnt)); 90 scanf("%lld", &q[0]); 91 for(LL i=1; i<n; ++i){ 92 scanf("%lld", &q[i]); 93 LL tmp=q[0]-q[i]>0 ? q[0]-q[i] : q[i]-q[0]; 94 if(tmp!=0){ 95 LL GCD=gcd(tmp, q[0]*q[i]); 96 solve(q[0]*q[i]/GCD); 97 q[i]=tmp/GCD; 98 } 99 else q[i]=0; 100 } 101 102 LL ans2=0; 103 for(LL i=1; i<n; ++i) 104 ans2=gcd(ans2, q[i]); 105 if(cnt[0]>0)//除以2 106 --cnt[0]; 107 else ans2*=2; 108 109 bigN(); 110 if(ans2==0){ 111 endx=0; 112 ans[endx]=0; 113 } 114 printf("%lld", ans[endx]); 115 for(int i=endx-1; i>=0; --i) 116 printf("%04lld", ans[i]); 117 printf(" %lld\n", ans2); 118 } 119 return 0; 120 }
1 //用java爽一下，處理大數 2 import java.util.Scanner; 3 import java.util.Arrays; 4 import java.math.*; 5 import java.io.BufferedInputStream; 6 class Main{ 7 static int[] tt = new int[1005]; 8 static int n; 9 static int top=0; 10 static boolean[] flag = new boolean[10005]; 11 static int[] p = new int[10005]; 12 static int[] q = new int[10005]; 13 static int[] aa = new int[10005]; 14 public static void isprime(){ 15 int i, j; 16 Arrays.fill(flag, false); 17 for(i=2; i<=10000; ++i){ 18 if(!flag[i]) p[top++]=i; 19 for(j=0; j<top && i*p[j]<=10000; ++j){ 20 flag[i*p[j]]=true; 21 if(i%p[j]==0) break; 22 } 23 } 24 --top; 25 flag[1]=true; 26 } 27 public static void solve(int k){ 28 int i, cnt; 29 for(i=0; i<=top && p[i]<=k; ++i){ 30 cnt=0; 31 while(k%p[i]==0){ 32 ++cnt; 33 k=k/p[i]; 34 } 35 if(cnt>aa[i]) 36 aa[i]=cnt; 37 } 38 } 39 40 public static int gcd(int a, int b){ 41 while(b!=0){ 42 int r=a%b; 43 a=b; 44 b=r; 45 } 46 return a; 47 } 48 49 50 public static void main(String[] args){ 51 isprime(); 52 Scanner input = new Scanner(new BufferedInputStream(System.in)); 53 n=input.nextInt(); 54 q[0]=input.nextInt(); 55 for(int i=1; i<n; ++i){ 56 q[i]=input.nextInt(); 57 int temp=Math.abs(q[0]-q[i]); 58 if(temp!=0){ 59 int GCD=gcd(temp, q[0]*q[i]); 60 solve(q[0]*q[i]/GCD); 61 q[i]=temp/GCD; 62 } 63 else q[i]=0; 64 } 65 66 BigInteger bigN = BigInteger.ONE; 67 for(int i=0; i<=top; ++i){ 68 for(int j=0; j<aa[i]; ++j) 69 bigN=bigN.multiply(BigInteger.valueOf(p[i])); 70 } 71 for(int i=0; i<=top; ++i) 72 if(aa[i]!=0) 73 System.out.println(p[i]+" "+aa[i]); 74 int ans=0; 75 for(int i=1; i<n; ++i){ 76 ans=gcd(ans, q[i]); 77 } 78 if(aa[0]>0) 79 bigN=bigN.divide(BigInteger.valueOf(2)); 80 else ans*=2; 81 if(ans==0) 82 bigN=BigInteger.ZERO; 83 System.out.println(bigN+" "+ans); 84 } 85 }
?
?
)
)
 強烈推薦!)
：logscape和logiq)