P3790 文艺数学题

    • 21通过
    • 136提交
  • 题目提供者will7101 管理员
  • 标签 洛谷原创 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    小Y在AK曼哈顿OI,CTSC和APIO之后,开始研究数学题。

    题目描述

    小Y有一张N个点,M条边的无向图(可能有重边、自环),每条边都有一个权值w。

    你需要计算:所有生成树的边权的最大公约数之和,具体操作见样例。

    生成树的定义:原图的一个连通子图,恰好有N-1条边。

    由于答案可能很大,需要对1000000007取模

    输入输出格式

    输入格式:

    第一行两个正整数N,M,表示点数和边数。

    接下来M行,每行三个正整数u,v,w,表示一条边连接u和v,权值为w。

    输出格式:

    输出一行一个数,表示答案对1000000007取模的值。

    输入输出样例

    输入样例#1: 复制
    4 5  
    1 2 12  
    1 3 9  
    2 4 6  
    3 4 8  
    1 4 4  
    输出样例#1: 复制
    15

    说明

    样例1的解释

    显然,这张图有8个不同的生成树。

    用$(x,y,z)$表示x,y,z的最大公约数,则答案

    $\=(12,6,8)+(6,8,9)+(8,9,12)+(9,12,6)+(9,4,6)+(12,4,8)+(12,4,9)+(6,4,8)\=2+1+1+3+1+4+1+2\=15$

    数据范围

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。