CA Loves GCD (BC#78 1002) (hdu 5656)
CA Loves GCD
Accepts: 135
Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
问题描述
CA喜欢是一个热爱党和人民的优秀同♂志，所以他也非常喜欢GCD（请在输入法中输入GCD得到CA喜欢GCD的原因）。 现在他有N个不同的数，每次他会从中选出若干个（至少一个数），求出所有数的GCD然后放回去。 为了使自己不会无聊，CA会把每种不同的选法都选一遍，CA想知道他得到的所有GCD的和是多少。 我们认为两种选法不同，当且仅当有一个数在其中一种选法中被选中了，而在另外一种选法中没有被选中。
输入描述
第一行 TT，表示有 TT 组数据。
接下来 TT 组数据，每组数据第一行一个整数 NN，表示CA的数的个数，接下来一行 NN 个整数 A_iAi 表示CA的每个数。
1 \le T \le 50,~1 \le N \le 1000,~1 \le A_i \le 10001≤T≤50,1≤N≤1000,1≤Ai≤1000
输出描述
对于每组数据输出一行一个整数表示CA所有的选法的GCD的和对 100000007100000007 取模的结果。
输入样例
2 2 2 4 3 1 2 3
输出样例
2.dp(i+1)(gcd(j,v))+=dp(i)(j)
3. dp(0)(0)=1
(
8 10
dp(i)(j):对前i个数gcd为j的方案数
1.dp(i+1)(j)+=dp(i)(j)2.dp(i+1)(gcd(j,v))+=dp(i)(j)
3. dp(0)(0)=1
(
i:1~1000
j:1~1000
j:1~1000
)
1、安卓版谍报馆客户端应用源码
2、git(基于apache)加大超时时间避免push失败
3、Sql Tips——Update语句也使用表别名(Table Alias)
4、vlc的流输出功能
5、helloPe的android项目实战之连连看—实现篇（一）
#include <cstdio> #include <cstring> int dp[1010][1010]; const int MOD=1e8+7; int gcd(int x,int y){return y==0?x:gcd(y,x%y);} int a[1010]; int gc[1010][1010]; int main() { for(int i=0;i<=1000;i++) { for(int j=i;j<=1000;j++) { gc[j][i]=gc[i][j]=gcd(i,j); } } int T; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); dp[0][0]=1; int n,v; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { for(int j=0;j<=1000;j++) { dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD; dp[i][gc[j][a[i]]]=(dp[i][gc[j][a[i]]]+dp[i-1][j])%MOD; } } long long ans=0; for(long long j=1;j<=1000;j++) ans=(ans+dp[n][j]*j)%MOD; printf("%lld\n",ans); } return 0; }View Code 优质内容筛选与推荐>>
1、安卓版谍报馆客户端应用源码
2、git(基于apache)加大超时时间避免push失败
3、Sql Tips——Update语句也使用表别名(Table Alias)
4、vlc的流输出功能
5、helloPe的android项目实战之连连看—实现篇（一）