P2926 [USACO08DEC]拍头Patting Heads

    • 757通过
    • 1.7K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 素数判断,质数,筛法 USACO 2008
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.

    Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly

    divisible by cow j's number A_j; she then sits again back in her original position.

    The cows would like you to help them determine, for each cow, the number of other cows she should pat.

    今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏.

    贝茜让N(1≤N≤100000)头奶牛坐成一个圈.除了1号与N号奶牛外,i号奶牛与i-l号和i+l号奶牛相邻.N号奶牛与1号奶牛相邻.农夫约翰用很多纸条装满了一个桶,每一张包含了一个不一定是独一无二的1到1,000,000的数字.

    接着每一头奶牛i从柄中取出一张纸条Ai.每头奶牛轮流走上一圈,同时拍打所有手上数字能整除在自己纸条上的数字的牛的头,然后做回到原来的位置.牛们希望你帮助他们确定,每一头奶牛需要拍打的牛.

    输入输出格式

    输入格式:

    * Line 1: A single integer: N

    * Lines 2..N+1: Line i+1 contains a single integer: A_i

    输出格式:

    * Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.

    输入输出样例

    输入样例#1: 复制
    5 
    2 
    1 
    2 
    3 
    4 
    
    输出样例#1: 复制
    2 
    0 
    2 
    1 
    3 
    

    说明

    The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

    The first cow pats the second and third cows; the second cows pats no cows; etc.

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