Cod sursa(job #2732659)

Utilizator Andy_ANDYSlatinaru Andrei Alexandru Andy_ANDY Data 29 martie 2021 10:05:20
Problema Indep Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;

ifstream f("indep.in");
ofstream g("indep.out");

int n,v[505];
int dp[505][1005];
int sum[505][1005];
main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>v[i];
        dp[i][v[i]]=1;
    }

    for(int i=1;i<=n;++i)
    {
        for(int gcd = 1; gcd <=1000; ++gcd)
        {   int k = __gcd(gcd,v[i]);
            dp[i][k] += sum[i-1][gcd];
        }
        for(int gcd = 1 ; gcd <= 1000 ; ++gcd )
        {
            sum[i][gcd] = sum[i-1][gcd]+dp[i][gcd];
        }
    }


    int ans = 0;
    for(int i=1;i<=n;++i)
        ans+=dp[i][1];
    g<<ans<< ' ';


    return 0;
}